Oszthatóság teljes indukcióval?

Mondjuk n=0-ra pont nem lesz igaz, mivel akkor a kifejezés értéke nem lesz egész.

Ha a nemnulla természetes számokra nézzük, akkor nézzük n=1 esetén: 5+2+1=8, 8|8, tehát igaz.

Tegyük fel, hogy n-ig igaz, nézzük meg, hogy n+1 esetén mi lesz a történet:

5^(n+1) + 2*3^(n+1-1) + 1 = 5^(n+1) + 2*3^n + 1

Használjuk a hatványozás azonosságait, és eközben arra törekszünk, hogy az eredeti alakot valahogy visszakapjuk:

= 5*5^n + 2*3*3^(n-1) + 1 = 5*5^n + 6*3^(n-1) + 1, ez szétszedhető így:

= [5^n + 2*3^(n-1) + 1] + 4*5^n + 4*3^(n-1)

A szögletes zárójelben az indukciós feltétel van, ez biztosan osztható 8-cal. A maradék tagokat még egy kicsit variáljuk oly módon, hogy kiemelünk 4-et:

4*(5^n + 3^(n-1)), ebből még ki tudunk emelni 2-t:

8*((5^n + 3^(n-1)/2), ez a szorzat már biztosan osztható 8-cal, amennyiben a zárójelben lévő rész egész. 5^n minden pozitív egész kitevőjű hatványa páratlan, ugyanez igaz 3^(n-1)-re is, páratlan+páratlan=páros, ezt pedig 2-vel osztva biztosan egész számot kapunk, tehát a 8*((5^n + 3^(n-1)/2) egy egész szám, ami osztható 8-cal.

Mivel így a kéttagú összeg minden tagja osztható 8-cal, ezért maga az összeg is, és ezt kellett belátnunk.