Teljes indukciós feladat átrendezése egy bizonyos formára, hogyan?

Kongruencia, avagy maradékos osztás:

x ≡ a mod m : x kongruens a modulus m-el. Azaz x/m maradéka a.

Kongruencia azonosságok:

x ≡ a mod m <=> x^n ≡ a^n mod m

x ≡ a mod m és y ≡ b mod m <=> x ° y ≡ a ° b mod m (° lehet +,-,*,/)

Ezek alapján

TI: menete:

1. lépés: példa első néhány n-re.

n=1 >> 207 ≡ 0 mod 9 OK

n=2 >> 873 ≡ 0 mod 9 OK

2. lépés: TIF (teljes indukciós feltétel)

TFH, igaz n-re, kell n+1 -re.

TFH, igaz n-re =>

10^n ≡ 1^n mod 9

5 ≡ 5 mod 9

ebből következik, hogy ha f(n) ≡ 0 mod 9, akkor 3*4^(2+n) ≡ 9-1-5 mod 9

9-1-5 = 3

3*4^(2+n) ≡ 3 mod 9

Kell n+1-re:

10^(n+1) ≡ 1^(n+1) mod 9

10^(n+1) ≡ 1 mod 9

5 ≡ 5 mod 9

3*4^(2+n) ≡ 4 mod 9 ==> 3*4^(2+n+1) ≡ 3*4 mod 9 ==>

3*4 = 12 = 9 + 3

3*4^(2+n+1) ≡ 9 + 3 mod 9

3*4^(2+n+1) ≡ 3 mod 9

Ebből következik, ha igaz n-re, igaz n+1-re.

3. lépés:

Bebizonyítottuk első néhány n-re.

Ha n-re igaz, akkor igaz n+1re.

Ezért a feltétel igaz.

Bocsi egyik sort elgépeltem:

3*4^(2+n) ≡ 4 mod 9 ==> 3*4^(2+n+1) ≡ 3*4 mod 9 ==>

Helyett!!!

3*4^(2+n) ≡ 3 mod 9 ==> 3*4^(2+n+1) ≡ 3*4 mod 9 ==>

Ha nem látod át a kongruenciát, akkor átfogalmazom. De a jelölést érdemes megszokni :)

- = [ n -re ] = -

10^n maradéka 9-el osztáskor mindig 1 lesz.

5 maradéka 9-el osztáskor mindig 5 lesz.

10^n + 3 * 4^(n+2) + 5 maradéka a feladat szerint n-re 0, mivel osztható 9-el.

Tehát 10^n + 3 * 4^(n+2) + 5 - (10^n) - (5) = 3 * 4^(n+2)

ennek a maradéka 0 - 5 - 1 = -6, ami ha 9-el való osztásnak a maradékát nézzük azonos, a 9 + (-6) = 3-al.

- = [ n+1 -re ] = -

10^(n+1) maradéka 9-el osztva mindig 1.

5 maradéka 9-el osztáskor mindig 5 lesz.

3 * 4^((n+1)+2) = 4 * (3 * 4^(n+2))

9-el való osztáskor 4*(3 * 4^(n+2)) maradéka = 4 * [3 * 4^(n+2) maradéka] = 4 * [3] = 12. Ha 12-t leosztjuk 9-el, a maradék 3 lesz. Tehát ugyan az a maradék az összeg minden tagjának n+1-re, mint n-re. Így a teljes össze maradéka szintén azonos lesz.

Na azért a kongruenciával jócskán bonyolult!

A(n)=10^n + 3 * 4^(n+2) + 5=

10^n + 48* 4^n + 5

ekkor

A(n+1)=10^(n+1) + 48*4^(n+1) + 5=

= 10*10^n + 192*4^n + 5=

= 10*(10^n + 48*4^n + 5)-288*4^n - 45=

= 10*A(n) - 288*4^n - 45

az ind. felt. miatt A(n) osztható 9-cel, továbbá 288 és 45 is osztható, ezért az A(n+1) kifejezés is osztható

ez érdemben könnyebb így, és ez volt a kérdés is