Part of ALG-10 — Mathematical Induction & Summation

Proving Divisibility by Induction

by Notetube Official74 words6 views

To prove "n3nn^{3-n} is divisible by 6 for all n>=1": Base case: n=1, 0 is divisible by 6. Inductive step: assume k3kk^{3-k} is divisible by 6. Show (k+1)^3-(k+1) = k^{3+3k}^{2+3k+1-k-1} = (k3kk^{3-k})+3k2+3kk^{2+3k} = (k3kk^{3-k})+3k(k+1). First term divisible by 6 (hypothesis). Second term: k(k+1) is always even, so 3k(k+1) is divisible by 6. Sum divisible by 6. JEE tests this pattern with numbers like 7^n-1 is divisible by 6, or 4^n-3n-1 is divisible by 9.

Like these notes? Save your own copy and start studying with NoteTube's AI tools.

Sign up free to clone these notes