Results 1 to 6 of 6

Math Help - Prove by induction

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    37

    Post Prove by induction

    Help please...

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,865
    Thanks
    728

    Re: Prove by induction

    What work have you done so far?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    37

    Post 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)!}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,475
    Thanks
    956

    Re: Prove by induction

    Quote Originally Posted by Deci View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,865
    Thanks
    728

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,696
    Thanks
    1467

    Re: Prove by induction

    Quote Originally Posted by Deci View Post
    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.
    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.
    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)!}
    Last edited by HallsofIvy; February 8th 2014 at 06:54 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help use induction to prove
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 29th 2012, 05:35 AM
  2. Prove using induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 13th 2011, 09:07 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Prove by induction?
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: March 1st 2010, 09:59 AM
  5. How to prove this by induction ?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 8th 2008, 11:46 AM

Search Tags


/mathhelpforum @mathhelpforum