# Prove by induction

• Feb 6th 2014, 02:29 AM
Deci
Prove by induction

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

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

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

where$\displaystyle \left(\begin{array}{cc}n\\r\end{array}\right) = \frac{n!}{r! (n-r)!}$ , do not use induction
• Feb 6th 2014, 03:23 AM
SlipEternal
Re: Prove by induction
What work have you done so far?
• Feb 7th 2014, 04:32 AM
Deci
Re: Prove by induction
For induction what I did is $\displaystyle 4^n + 14 = 6N$
for n = 1
$\displaystyle 4^1 + 14 = 18 = 6 x 3$

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

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

and for (2)

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

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

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

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

$\displaystyle = \frac{n! n!}{(r+1)! r! (n-r)! (n-r-1)!}$
• Feb 7th 2014, 05:57 AM
romsek
Re: Prove by induction
Quote:

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

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

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

and for (2)

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

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

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

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

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

1) let $\displaystyle 4^n+14=6k$

\displaystyle \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 $\displaystyle \left( \begin{array}{c}n+1 \\ r+1 \end{array}\right)$ and see what you get.
• Feb 7th 2014, 01:34 PM
SlipEternal
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.
• Feb 8th 2014, 06:49 AM
HallsofIvy
Re: Prove by induction
Quote:

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

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

for n = k+1
$\displaystyle 4^{k+1} + 14 = 6N$
$\displaystyle (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.
Instead start with 4^{k+1}+ 14= 4(4^k)+ 14= 3(4^k)+ 4^k+ 14= 3(4^k)+ 6N.
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.
Quote:

$\displaystyle 2(4^k) +18 = 6N$

and for (2)

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

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

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

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

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