×

# Good use of induction!!!

This is related to the Previous note about Induction

Out of the problems stated in the note, $$(a)$$ to $$(d)$$ and $$(f)$$ are standard results, you can use them like identities.

Here's the proof of $$(e)$$ which is slightly different than other ones.

Problem is to prove that $$24 \mid (2\cdot 7^n+3\cdot 5^n -5)$$ ...... $$\forall n\in \mathbb{N}$$

Observe that for $$n=1$$, we have $$2\cdot 7^n+3\cdot 5^n -5 = 14+15-5=24$$. Hence the result is true for $$1$$.

Assume that the result is $$\color{Blue}{TRUE}$$ for $$n=k$$, and we'll prove for $$n=k+1$$

For this, we use a $$\color{Green}{\text{little manipulation}}$$.

Consider the term $$2\cdot 7^{k+1} +3\cdot 5^{k+1} -5$$.

This term is equivalent to $$7(2\cdot7^k +3\cdot 5^k -5) - 6\cdot 5^k +30$$ ...... this is because $$7\times 3 \cdot 5^k - 6\cdot 5^k = (21-6)5^k = 3\cdot 5^{k+1}$$ and this term we want in our proof!!!

Returning to the proof, we have assumed that the result is true for $$n=k$$, hence in the term, i.e.

$$\displaystyle 2\cdot 7^{k+1} +3\cdot 5^{k+1} -5 =7 \underbrace{(2\cdot 7^k +3\cdot 5^k -5)}_{\text{divisible by 24 by assumption}} - 6\cdot 5^k +30$$

Thus what only remains to prove is $$-6\cdot 5^k +30$$ is divisible by 24, see that

$$-6\cdot 5^k+30= -6(5^k-5)$$. So the problem has reduced to proving $$24\mid -6(5^k -5)$$ or even simpler, $$4 \mid 5^k-5$$

We know that $5 \equiv 1\pmod{4}\implies 5^k \equiv 1 \pmod{4}$

And $$5^k\equiv 5\equiv 1 \pmod{4} \implies 5^k-5\equiv 1-1\equiv 0 \pmod{4}$$

Hence $$4 | 5^k-5$$ . Hence the other term in the expression is also divisible by 24, thus if the result is $$assumed$$ to be true for $$n=k$$ then we are $$obtaining$$ it to be true for $$n=k+1$$ and for $$n=1$$ we already proved, thus it's true for $$ALL$$ natural numbers.

2 years, 3 months ago

Sort by:

Good one · 2 years, 1 month ago