Lesson 45

Aim: Induction problems involving divisibility

Do Now: 1*2+3*4+5*6+…(2n+1)(2n)=[n*(n+1)(4n-1)]/3

Base Case: n=1

2=1*2(4-1)/3

2=2

Assume that if n=k is true, then n=k+1 is also true

Assume that n=k is true

1*2+3*4+5*6+…(2k+1)(2k)=[k*(k+1)(4k-1)]/3

n=k+1

1*2+3*4+5*6+…(2k+1)(2k)+[(2(k+1))+1]2(k+1)=?[[k+1*(k+2)[(4(k+1))-1]]/3

k(k+1)(4k-1)/3 + (2k+3)(2k+2) =? (k+1)(k+2)(4k+3)/3

[k(k+1)(4k-1) + [3(2k+3)(2k+2)]]/3 =? RHS

[k(4k^2 +3k -1) + [3(4k^2 +10k + 60]]/3]]=? RHS

(4k^3 + 3k^2 - k + 12k^2 + 30k + 18)/3=? RHS

(4k^3 + 15k^2 + 29k + 18)/3=? RHS

[(k+1)(4k^2 +11k +18)]/3=? RHS

[(k+1)(4k+3)(k+2)]/3= RHS
Prove that (6^n)-1 is divisble by 5 for n>=1, integer

5l(6^n)-1

Base Case: n=1

6-1=5

Still assume true for n=k

5l(6^k)-1

Then for n=k+1

(6^k+1)-1=6^k*6-1

=6(6^k)-1

=6(6^k)-6+5

=6(6^k-1)+5
Prove that (2^2n)-1 is divisible by 3 for n>= 1

Base Case: n=1

(2^2)-1=3

Still assume if true for n=k

3l(2^2k)-1

Then for n=k+1

(2^2(k+1))-1=2^(2k+2)-1=2^2k(2^2)-1=4(2^2k)-1=4(2^2k)-4+3=4((2^2k)-1)+3
Prove that 5 goes into (n^5)-n for all n greater than or equal to 2

Base Case: (2^5)-2=32-2=30

Assume true for n=k

5l(k^5)-k

Then for n=k+1

(k+1)^5 - (k+1)=

Fibonacci sequence

k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 - k - 1

((k^5)-k)+5(k^4 + 2k^3 + 2k^2 + k)
Ying Xie Period 10