# Math Help - Prove by induction

1. ## Prove by induction

1) Use the method of mathematical induction to prove that $4^n + 14$ is a multiple of 6 for n $\geq$ 1

2) For positive integers n and r, with r $\lesthn$ n, show that

$\left(\begin{array}{cc}n\\r\end{array}\right)$ $\left(\begin{array}{cc}n\\r+1\end{array}\right)$ $= \left(\begin{array}{cc}n+1\\r+1\end{array}\right)$

where $\left(\begin{array}{cc}n\\r\end{array}\right) = \frac{n!}{r! (n-r)!}$ , do not use induction

2. ## Re: Prove by induction

What work have you done so far?

3. ## Re: Prove by induction

For induction what I did is $4^n + 14 = 6N$
for n = 1
$4^1 + 14 = 18 = 6 x 3$

for n = k
$4^k + 14 = 6N$

for n = k+1
$4^{k+1} + 14 = 6N$
$(4^{k} + 14) + 4^{k+1} + 14 = 6N$
$2(4^k) +18 = 6N$

and for (2)

since $\left(\begin{array}{cc}n\\r\end{array}\right) = \frac{n!}{r! (n-r)!}$,

so
$\left(\begin{array}{cc}n\\r\end{array}\right) \left(\begin{array}{cc}n\\r+1\end{array}\right) =$

$\frac{n!}{r! (n-r)!} \frac{n!}{(r+1)! (n-(r+1))!}$

$= \frac{n!}{r! (n-r)!} \frac{n!}{(r+1)! (n-r-1)!}$

$= \frac{n! n!}{(r+1)! r! (n-r)! (n-r-1)!}$

4. ## Re: Prove by induction

Originally Posted by Deci
For induction what I did is $4^n + 14 = 6N$
for n = 1
$4^1 + 14 = 18 = 6 x 3$

for n = k
$4^k + 14 = 6N$

for n = k+1
$4^{k+1} + 14 = 6N$
$(4^{k} + 14) + 4^{k+1} + 14 = 6N$
$2(4^k) +18 = 6N$

and for (2)

since $\left(\begin{array}{cc}n\\r\end{array}\right) = \frac{n!}{r! (n-r)!}$,

so
$\left(\begin{array}{cc}n\\r\end{array}\right) \left(\begin{array}{cc}n\\r+1\end{array}\right) =$

$\frac{n!}{r! (n-r)!} \frac{n!}{(r+1)! (n-(r+1))!}$

$= \frac{n!}{r! (n-r)!} \frac{n!}{(r+1)! (n-r-1)!}$

$= \frac{n! n!}{(r+1)! r! (n-r)! (n-r-1)!}$
1) let $4^n+14=6k$

\begin{align*}&4^{n+1}+14 = \\&4\cdot 4^n + 14 = \\&4(4^n+14)-56+14 = \\&4(6k)-7(6) = \\&(4k-7)6\end{align}

2) you gave up too early. Expand $\left( \begin{array}{c}n+1 \\ r+1 \end{array}\right)$ and see what you get.

5. ## Re: Prove by induction

For (2), you wrote the problem wrong. 3 choose 1 times 3 choose 2 = 9 while 4 choose 2 = 6. Now, adding them will be correct. 3 choose 1 plus 3 choose 2 = 6 = 4 choose 2. Then, romsek's advice to expand n+1 choose r+1 is helpful.

6. ## Re: Prove by induction

Originally Posted by Deci
For induction what I did is $4^n + 14 = 6N$
for n = 1
$4^1 + 14 = 18 = 6 x 3$

for n = k
$4^k + 14 = 6N$

for n = k+1
$4^{k+1} + 14 = 6N$
$(4^{k} + 14) + 4^{k+1} + 14 = 6N$
This is non-sense. Having already said that 4^{k+1}+ 14= 6N adding the positive number 4^k+ 14 it won't still be "6N". In any case, your previous statement " 4^{k+1}+ 14= 6N" is not possible because you have already said that 4^k+ 14= 6N. The can't both be equal to the same number. You could say "4^{k+1}+ 14= 6M" for some "M", not necessarily "N". But that is what you want to prove- you cannot assert it yet.
Now use the fact that 4= 2^2 to write 4^k= (2^2)^k= 2^{2k} so that the above is 3(2)(2^{2k-1})+ 6N= 6(2^{2k-1}+ N)

The "tex" tags are not working so I took them out.
$2(4^k) +18 = 6N$

and for (2)

since $\left(\begin{array}{cc}n\\r\end{array}\right) = \frac{n!}{r! (n-r)!}$,

so
$\left(\begin{array}{cc}n\\r\end{array}\right) \left(\begin{array}{cc}n\\r+1\end{array}\right) =$

$\frac{n!}{r! (n-r)!} \frac{n!}{(r+1)! (n-(r+1))!}$

$= \frac{n!}{r! (n-r)!} \frac{n!}{(r+1)! (n-r-1)!}$

$= \frac{n! n!}{(r+1)! r! (n-r)! (n-r-1)!}$