# Math Help - Mathematical induction problems

1. ## Mathematical induction problems

I'm left with these problems to do if anyone can help with any or all of them. Could you while helping me solve the problems try to explain in details especially with the proofs as this is one of my weaker sections in discrete maths. Thanks in advance.

1) Prove by mathematical induction that all positive integers n,

a)1*2+2*3+3*4...n(n+1)=n(n+1)(n+2)/3
b)1/(1*3)+1/(3*5)+1/(5*7)+...+1/(2n-1)(2n+1)=n/2n+1
c)(5^2n)-1 is divisible by 24
d) 1^2-2^2+3^2...((-1)^n+1)n^2=((-1)^n+1)n(n+1))/2

2) Prove by mathematical induction
a) that 2n+1<=2^n for n=3,4,...
b)Use part (a) in the proof that 2^n>=n^2 for n=4,5,...

3) Use mathematical induction to show that postage of 5 cents or more can be achieved by using only 2 cents and 5 cent stamps(as many of each is needed.

2. Hello, aloufy!

I will assume you already know the basics of Induction.
I'll do a few of these . . .

Prove by mathematical induction:

$a)\;\;1\cdot2+2\cdot3+3\cdot4 + \cdots + n(n+1) \;=\;\frac{n(n+1)(n+2)}{3}$
Verify $S(1)\!:\;\;1\cdot2 \:=\:\frac{1\cdot2\cdot3}{3}\quad\Rightarrow\quad 2\:=\:2$ . . . true!

Assume $S(k)\!:\;\;1\cdot2 + 2\cdot3 + 3\cdot 4 + \cdots + k(k+1)\;=\;\frac{k(k+1)(k+2)}{3}$

Add $(k+1)(k+2)$ to both sides:
. . $1\cdot2\,+\,2\cdot 3\,+\,\cdots +\,k(k+1) {\color{blue}\,+\,(k+1)(k+2)} \;=\;\frac{k(k+1)(k+2)}{3}{\color{blue}\,+\,(k+1)( k+2)}$

On the right side, factor: . $((k+1)(k+2)\left[\frac{k}{3} + 1\right] \;=\;(k+1)(k+2)\left(\frac{k+3}{3}\right)$

And we have:
. . $1\cdot2 + 2\cdot 3 + 3\cdot4 + \cdots + (k+1)(k+2) \;=\;\frac{(k+1)(k+2)(k+3)}{3}$

And we shown that $S(k+1)$ is true.
. . The inductive proof is compete.

$c)\;\;5^{2n} -1$ is divisible by 24

Verify $S(1)\!:\;\;5^2-1 \:=\:24$ . . . True!

Assume $S(k)\!:\;\;5^{2k} - 1 \:=\:24a$ for some integer $a.$

Add $24\cdot5^{2k}$ to both sides: . $5^{2k}\,{\color{blue}+\,24\cdot5^{2k}}-1\;=\;24a\,{\color{blue}+\,24\cdot5^{2k}}$

. . The left side is: . $5^{2k}[1 + 24] - 1 \;=\;5^{2k}\cdot25 - 1 \;=\;5^{2k}\cdot5^2 - 1 \;=\;5^{2k+2} - 1\;=\;5^{2(k+1)} - 1$

. . The right side is: . $24a + 24\cdot5^{2k} \;=\;24(a + 5^{2k})$

$\text{Hence we have: }\;5^{2(k+1)} - 1 \;=\;\underbrace{24\left(a + 5^{2k}\right)}_{\text{multiple of 24}}$

Therefore, we have proved $S(k+1).$
. . The inductive proof is complete.

3. Originally Posted by Soroban
Hello, aloufy!

I will assume you already know the basics of Induction.
I'll do a few of these . . .

Verify $S(1)\!:\;\;1\cdot2 \:=\:\frac{1\cdot2\cdot3}{3}\quad\Rightarrow\quad 2\:=\:2$ . . . true!

Assume $S(k)\!:\;\;1\cdot2 + 2\cdot3 + 3\cdot 4 + \cdots + k(k+1)\;=\;\frac{k(k+1)(k+2)}{3}$

Add $(k+1)(k+2)$ to both sides:
. . $1\cdot2\,+\,2\cdot 3\,+\,\cdots +\,k(k+1) {\color{blue}\,+\,(k+1)(k+2)} \;=\;\frac{k(k+1)(k+2)}{3}{\color{blue}\,+\,(k+1)( k+2)}$

On the right side, factor: . $((k+1)(k+2)\left[\frac{k}{3} + 1\right] \;=\;(k+1)(k+2)\left(\frac{k+3}{3}\right)$

And we have:
. . $1\cdot2 + 2\cdot 3 + 3\cdot4 + \cdots + (k+1)(k+2) \;=\;\frac{(k+1)(k+2)(k+3)}{3}$

And we shown that $S(k+1)$ is true.
. . The inductive proof is compete.

Verify $S(1)\!:\;\;5^2-1 \:=\:24$ . . . True!

Assume $S(k)\!:\;\;5^{2k} - 1 \:=\:24a$ for some integer $a.$

Add $24\cdot5^{2k}$ to both sides: . $5^{2k}\,{\color{blue}+\,24\cdot5^{2k}}-1\;=\;24a\,{\color{blue}+\,24\cdot5^{2k}}$

. . The left side is: . $5^{2k}[1 + 24] - 1 \;=\;5^{2k}\cdot25 - 1 \;=\;5^{2k}\cdot5^2 - 1 \;=\;5^{2k+2} - 1\;=\;5^{2(k+1)} - 1$

. . The right side is: . $24a + 24\cdot5^{2k} \;=\;24(a + 5^{2k})$

$\text{Hence we have: }\;5^{2(k+1)} - 1 \;=\;\underbrace{24\left(a + 5^{2k}\right)}_{\text{multiple of 24}}$

Therefore, we have proved $S(k+1).$
. . The inductive proof is complete.

Thanks Soroban "big help"...Can anyone help me with the other problems?