WisFaq!

Volledige inductie

3²ⁿ⁺¹+ 2^n-1 is deelbaar door 7

Peter
6-11-2002

Antwoord

Hoi,

Voor n=0 geldt de stelling niet.

De basisstap:
Voor n=1 geldt ze wel: 3³+2⁰=27+1=28 en 7|28.

De inductiestap:
Als de stelling geldt voor k=1,2,..,n-1 dan geldt ze ook voor n.

3²ⁿ⁺¹+2^n-1=
3^2(n-1)+1+2+2^(n-1)-1+1=
3².3^2(n-1)+1+2¹.2^(n-1)-1=
9.3^2(n-1)+1+2.2^(n-1)-1=

Nu weten we dat 7|3^2(n-1)+1+2^(n-1)-1 (veronderstelling van inductiestap) en dus ook: 7|2.3^2(n-1)+1+2.2^(n-1)-1

Uiteraard is 7|7.3^2(n-1)+1

Zodat na samentellen: 7|(2+7).3^2(n-1)+1+2.2^(n-1)-1. Hiermee is de inductiestap en de stelling bewezen.

Groetjes,
Johan

PS:
Je kan het natuurlijk ook rechtstreeks bewijzen:
3²ⁿ⁺¹+2^n-1 (mod 7) = 3.9ⁿ+2^n-1 (mod 7) = 3.2.2^n-1+2^n-1 (mod 7) = 7.2^n-1 (mod 7)= 0

andros
6-11-2002