I'm on my quest to understand mathematical induction proofs (beginners). First, thanks to How to use mathematical induction with inequalities? I kinda understood better the procedure, and practiced it with Is this induction procedure correct? ($2^n
So far I've been doing equalities and inequalities. Alright. When things seemed to get better now I'm asked to prove divisibility.
My book has an exercise with the solution, but there is a part I don't get well:
With $n\ge1$ prove:
$n(n+1)(n+2)$ is divisible by 6.
Assume $$\exists k[n(n+1)(n+2) = 6k]$$ For the inductive step and
using distribution: $$(n+1)(n+2)(n+3) = n(n+1)(n+2)+3(n+1)(n+2)$$
$$=6k+3\cdot2k'$$ $$=6(k+k') = 6k''$$
Alright. I see where is that $6k$ coming from, but what about the $3\cdot2k'$? How does the $3(n+1)(n+2)$ we had become that?
That's it for the example I didn't understand well. But I also tried doing another exercise by myself (and didn't manage to do it):
Prove, with $n\ge1$:
$10^n+3\cdot4^{n+2}+5$ is divisible by $9$.
First, I prove it for $n+1$:
To do so we need to show that $\exists x[10^1+3\cdot4^{1+2}+5=9x]$. It holds, because $(10^1+3\cdot4^{1+2}+5) = (10+3\cdot16+5) = (15+48) = 63 = 9 \cdot 7$
Now we assume
$$\exists x[10^n+3\cdot4^{n+2}+5=9x]$$
We need to prove it for $n+1$:
$$10^{n+1}+3\cdot4^{n+3} = 10^n\cdot10+3\cdot4^n\cdot4^3$$
$$= 10^n\cdot10+3\cdot4^{n+2}\cdot4$$
$$=(9x-3\cdot4^{n+2}-5)\cdot10+(3\cdot4^{n+2}\cdot4)$$
By this point I don't even know what I'm doing. I though that I could use $10^n$ with the inductive assumption and replace it with $(9x-3\cdot4^{n+2}-5)$, similar to what the book did before. But now the situation looks worse.
Similarly to this question How to use mathematical induction with inequalities?, I seek to understand mathematical induction when applied to divisibility cases this time. It seems (for me) that all these cases (equalities, inequalities and divisibility) do have important differences at the moment of solving.
Answer
There is a simpler theorem of this type and that brings us the $2k'$: With $n\ge 1$ prove that $n(n+1)$ is amultiple of $2$.
Remark: You should now be able to prove with yet another induction that $\frac{(n+k)!}{(n-1)!}=n(n+1)\cdots (n+k)$ is a multiple of $k!$.
Your other attempt is fine so far.
Note that $$(9x-3\cdot 4^{n+2}-5)\cdot 10+(3\cdot 4^{n+2}\cdot4) = 90x-18\cdot 4^{n+2}-50\\=9\cdot(10x-2\cdot 4^{n+2}-5)-5.$$
No comments:
Post a Comment