7^n + 3^n+1 osztható 4-el?

Kipróbálod n=1-re:

7+9=16, osztható 4-el.

Felteszed, hogy n=k-ra igaz:

4|7^k+3^(k+1)

A feltevést felhasználva meg kell mutatni, hogy k+1-re is igaz:

4|7^(k+1)+3^(k+2)

Kezdjük el átalakítani:

7^(k+1) = 7*7^k

3^(k+2) = 3*3^(k+1)

7^(k+1)+3^(k+2) = 7*7^k+3*3^(k+1) =

7 = 8-1

3= 4-1

= (8-1)*7^k + (4-1)*3^(k+1) =

= 8*7^k + 4*3^(k+1) - 7^k - 3^(k+1) =

= 4 * (2*7^k+3^(k+1) ) - (7^k + 3^(k+1))

Vagyis az első tag 4-el osztható, amiből ki van vonva egy másik szám, ami az indukciós feltevés szerint szintén 4-el osztható.

Ezzel kész a bizonyítás.