Proof by Mathematical Induction

Question

7a. Prove by Mathematical Induction that $4^{n+1}+5^{2n-1}$ is divisible by $21$.

Answer 1

Let $f(n)=4^{n+1}+5^{2n-1}$. We are attempting to prove that $21\mid f(n)$ for all $n$.

Ok, so to prove by induction requires two steps: first, prove that it is true when $n=1$; second, show that $f(n)\implies f(n+1)$.

To show the first part is trivial: $f(1) = 4^{(1)+1}+5^{2(1)-1}=4^2 + 5^1 = 16+5=21$. So $f(1)$ is clearly divisible by 21.

Next, assume that $f(n)$ is divisible by 21. We evaluate $f(n+1)$:

$$f(n+1)= 4^{(n+1)+1}+5^{2(n+1)-1}$$ $$ = 4(4^{n+1}) + 5^2(5^{2n-1})$$ $$ = 4(4^{n+1}+5^{2n-1}) + 21(5^{2n-1}) $$ $$ = 4\cdot f(n) + 21(5^{2n-1}) $$

Therefore, if $f(n)$ is divisible by 21, then so is $f(n+1)$. Thus, the rule holds for all natural numbers $n$.