Bizonyítás (? )

Az első könnyű: Ha n legalább 1 értékű egész szám, akkor a kifejezés mindkét tagja páros, hisz az első tag 2 hatvánnyal van szorozva, a második tag meg 64-gyel. 5 páratlan többszörösei pedig páratlanok, tehát N nem lehet olyan.

Ha a nulla is természetes szám lenne, akkor meg kellene arra külön is nézni, mert 2^0 = 1 nem páros, ezért olyankor az első tag páratlan, a második páros, tehát N páratlan. (Akkor egyébként N = 9·1 + 64·1 = 73, az nem osztható 5-tel, OK.)

A második bonyolultabb. Tanultátok a teljes indukciót?

A nulla nem természetes szám, de most mégis érdemes abból kiindulni, mert azzal könnyebb kiszámolni N-et. Szóval egy bővebb dolgot fogok bebizonyítani: nem csak természetes számokra, hanem nemnegatív egész n-ekre is osztható N 73-mal:

Nézzük tehát n=0 esetén. Ekkor N=73, vagyis igaz az állítás.

Most jön az indukciós feltevés:

Feltételezem, hogy egy valamilyen n=k értékre igaz az állítás, vagyis

9·2^(3k) + 64·3^(4k) = 73·c

Nézzük meg, hogy n=k+1 esetén is igaz lesz-e?

Az egyszerűsítés céljából nevezzük el az n=k-hoz tartozó tagokat a és b-nek:

9·2^(3k) = a

64·3^(4k) = b

N = a + b = 73·c

Nem lenne muszáj ilyen elnevezéseket csinálni, de ezekkel kevesebbet kell majd írni és jobban látszik a dolog.

Most n=k+1 esetén így alakul N:

N = 9·2^(3k+3) + 64·3^(4k+4) = 9·2^(3k)·2^3 + 64·3^(4k)·3^4 = a·2^3 + b·3^4 = 8a + 81b

Mivel 81 = 73+8:

N = 8a + (73+8)b = 8a + 73b + 8b = 8(a+b) + 73b = 8·73c + 73b = 73·(8c + b)

Vagyis tényleg osztható 73-mal n=k+1-re is.

A teljes indukciós bizonyítás kész is.

Magyarázat, hogy miért bizonyítja ez be:

n=0-ra igaz volt, hogy N osztható 73-mal, mert leellenőriztük. Mivel n=k-ról n=k+1-re be tudtuk látni, hogy öröklődik ez a tulajdonság, ezért n=0-ról is öröklődik n=1-re, onnan tovább n=2-re, stb., az összes természetes számra.