Results 1 to 13 of 13
Like Tree8Thanks
  • 2 Post By romsek
  • 2 Post By JeffM
  • 1 Post By mathman11
  • 1 Post By HallsofIvy
  • 2 Post By JeffM

Math Help - induction help

  1. #1
    Member
    Joined
    Jun 2014
    From
    In ah House
    Posts
    75
    Thanks
    2

    induction help

    Can someone post a solution to this question along with an explanation please? I got a test tomorrow and im having trouble understanding this.

    Prove by induction:

    4^n+1 + 5^n-1 is divisible by 21 n ∈ N,n>=1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,789
    Thanks
    1147

    Re: induction help

    Quote Originally Posted by mathman11 View Post
    Can someone post a solution to this question along with an explanation please? I got a test tomorrow and im having trouble understanding this.

    Prove by induction:

    4^n+1 + 5^n-1 is divisible by 21 n ∈ N,n>=1
    I'm guessing you mean

    $4^{n+1}+5^{n-1}$ is divisible by $21, ~~\forall n \in \mathbb{N}, n\geq 1$

    But maybe not since

    $n=1 \Rightarrow 4^2+1=17 \neq 21k$

    $n=2 \Rightarrow 4^3+5 = 69 \neq 21k$

    I show that in general your statement is incorrect.

    Could you repost the correct statement you're trying to prove?
    Thanks from topsquark and HallsofIvy
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2014
    From
    In ah House
    Posts
    75
    Thanks
    2

    Re: induction help

    Quote Originally Posted by romsek View Post
    I'm guessing you mean

    $4^{n+1}+5^{n-1}$ is divisible by $21, ~~\forall n \in \mathbb{N}, n\geq 1$

    But maybe not since

    $n=1 \Rightarrow 4^2+1=17 \neq 21k$

    $n=2 \Rightarrow 4^3+5 = 69 \neq 21k$

    I show that in general your statement is incorrect.

    Could you repost the correct statement you're trying to prove?
    this is the correct statement
    $4^{n+1}+5^{n-1}$ is divisible by $21, ~~\forall n \in \mathbb{N}, n\geq 1$
    i proved the base case for n=1 to be divisible by 21. and its true. If you can do the other part of the solution id appreciate it very much.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    817
    Thanks
    410

    Re: induction help

    Quote Originally Posted by mathman11 View Post
    this is the correct statement
    $4^{n+1}+5^{n-1}$ is divisible by $21, ~~\forall n \in \mathbb{N}, n\geq 1$
    i proved the base case for n=1 to be divisible by 21. and its true. If you can do the other part of the solution id appreciate it very much.
    Romsek has given TWO examples showing that what you are trying to prove is false.

    In particular, he has shown that your base case is false. Let's go over it again.

    $n = 1 \implies 4^{(n + 1)} = 4^2 = 16\ and \ 5^{(n - 1)} = 5^0 = 1 \implies$

    $4^{(n + 1)} + 5^{(n - 1)} = 16 + 1 = 17,$ which is clearly not divisible by 21.

    Perhaps if you showed how you "proved" it true if n = 1, we could figure out what the problem actually is.
    Thanks from topsquark and HallsofIvy
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2014
    From
    In ah House
    Posts
    75
    Thanks
    2

    Re: induction help

    Quote Originally Posted by JeffM View Post
    Romsek has given TWO examples showing that what you are trying to prove is false.

    In particular, he has shown that your base case is false. Let's go over it again.

    $n = 1 \implies 4^{(n + 1)} = 4^2 = 16\ and \ 5^{(n - 1)} = 5^0 = 1 \implies$

    $4^{(n + 1)} + 5^{(n - 1)} = 16 + 1 = 17,$ which is clearly not divisible by 21.

    Perhaps if you showed how you "proved" it true if n = 1, we could figure out what the problem actually is.
    I missed out an n term. The statement supposed to read:
    4^{(n + 1)} + 5^{(2n - 1)} is divisible by 21.

    Base Case: n=1

    4^{(1 + 1)} + 5^{(2(1) - 1)}
    4^{(2)} + 5^{(2 - 1)}
    4^{(2)} + 5^{(1)}
    16 + 5 = 21 --> divisible by 21
    Last edited by mathman11; July 10th 2014 at 08:42 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,413
    Thanks
    1852

    Re: induction help

    Okay so the "inductive hypothesis" is that 4^{k+1}+ 5^{2k-1}= 21m for some integer m.

    Then 4^{(k+1)+ 1}+ 5^{2(k+1)- 1}= 4(4^{k+1})+ 25(5^{2k-1})= 4(4^{k+1}+ 5^{2k-1})+ 21(5^{2k-1})

    Can you finish from here?
    Last edited by HallsofIvy; July 10th 2014 at 10:37 AM.
    Thanks from JeffM
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2014
    From
    In ah House
    Posts
    75
    Thanks
    2

    Re: induction help

    Quote Originally Posted by HallsofIvy View Post
    Okay so the "inductive hypothesis" is that 4^{k+1}+ 5^{2k-1}= 21m for some integer m.

    Then 4^{(k+1)+ 1}+ 5^{2(k+1)- 1}= 4(4^{k+1})+ 25(5^{2k-1})= 4(4^{k+1}+ 5^{2k-1})+ 21(5^{2k-1})

    Can you finish from here?
    yes i think i can do it from here but can you explain to me how you got 21(5^2k -1)?
    thanks
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    817
    Thanks
    410

    Re: induction help

    Quote Originally Posted by mathman11 View Post
    yes i think i can do it from here but can you explain to me how you got 21(5^2k -1)?
    thanks
    $4\left(4^{(k+1)}\right) + 25\left(5^{(2k - 1)}\right) = 4\left(4^{(k+1)}\right) + 4\left(5^{(2k - 1)}\right) + 21\left(5^{(2k - 1)}\right) =4\left(4^{(k+1)}\ + 5^{(2k - 1)}\right) + 21\left(5^{(2k - 1)}\right) $
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2014
    From
    In ah House
    Posts
    75
    Thanks
    2

    Re: induction help

    Quote Originally Posted by JeffM View Post
    $4\left(4^{(k+1)}\right) + 25\left(5^{(2k - 1)}\right) = 4\left(4^{(k+1)}\right) + 4\left(5^{(2k - 1)}\right) + 21\left(5^{(2k - 1)}\right) =4\left(4^{(k+1)}\ + 5^{(2k - 1)}\right) + 21\left(5^{(2k - 1)}\right) $
    i still dont see how or where 21 came from.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    817
    Thanks
    410

    Re: induction help

    He separated $25 * 5^{(2k - 1)}\ into\ 4 * 5^{(2k - 1)} + 21 * 5^{(2k - 1)}.$

    The general idea is this $25a = 4a + 21a.$ In this case the $a = 5^{(2k - 1)}.$
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2014
    From
    In ah House
    Posts
    75
    Thanks
    2

    Re: induction help

    Quote Originally Posted by JeffM View Post
    He separated $25 * 5^{(2k - 1)}\ into\ 4 * 5^{(2k - 1)} + 21 * 5^{(2k - 1)}.$

    The general idea is this $25a = 4a + 21a.$ In this case the $a = 5^{(2k - 1)}.$
    ok but how does one prove for (k+1) from that.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    817
    Thanks
    410

    Re: induction help

    I am going to give you this one so you see the logic of a proof by induction. As for finding a proof of any kind, there is no rule book: it takes creativity.

    $H\ is\ the\ set\ such\ that\ n \in H \implies n \in\ \mathbb N,\ n \ge 1,\ and\ \dfrac{4^{n + 1} + 5^{2n - 1}}{21} \in \mathbb N.$ But H may be the empty set.

    $1 \in \mathbb N,\ and\ 1 \ge 1,\ and\ \dfrac{4^{1 + 1} + 5^{2 * 1 - 1}}{21} = \dfrac{4^2 + 5^1}{21} = \dfrac{16 + 5}{21} = \dfrac{21}{21} = 1 \in \mathbb N.$

    This is just arithmetic and you got it but it implies something very important, namely:

    $\therefore 1 \in H.$ You have proved that H is not empty.

    Now we choose an arbitrary member of H and call it k. This is called an inductive hypothesis for reasons that elude me because we have proved that at least one such number exists.

    $Let\ k\ be\ an\ arbitrary\ member\ of\ H \implies k \in\ \mathbb N,\ k \ge 1,\ and\ \dfrac{4^{k + 1} + 5^{2k - 1}}{21} \in \mathbb N.$

    $Let\ m = \dfrac{4^{k + 1} + 5^{2k - 1}}{21} \implies m \in \mathbb N\ and\ 4^{k + 1} + 5^{2k - 1} = 21m.$ With me to here?

    Now we want to prove that k + 1 is also a member of H. It's trivially obvious that k + 1 is a natural number greater than or equal to 1 because those things are true of k. So the trick is to prove that the third condition for membership in H is met by k + 1. Very generally, you do that by finding out a way to reduce that third condition for k + 1 into something related to that same condition for k. This may require virtually no creativity or a lot of it. It is what makes proofs an art. Halls of Ivy came up with this bit of creativity starting from setting up the relevant expression for k + 1.

    $\dfrac{4^{(k + 1) + 1} + 5^{2(k + 1) - 1}}{21} = \dfrac{4^{k + 2} + 5^{2k + 1}}{21} = \dfrac{4\left(4^{k + 1}\right) + 25\left(5^{2k - 1}\right)}{21} = \dfrac{4\left(4^{k + 1}\right) + 4\left(5^{2k - 1}\right) + 21\left(5^{2k - 1}\right)}{21} = $

    $\dfrac{4\left(4^{k + 1} + 5^{2k - 1}\right) + 21\left(5^{2k - 1}\right)}{21} = \dfrac{4\left(21m\right) + 21\left(5^{2k - 1}\right)}{21} = \dfrac{21\left(4m + 5^{2k - 1}\right)}{21} = 4m + 5^{2k - 1}.$

    $But\ 4m\ and\ 5^{2k - 1} \in \mathbb N \implies 4m + 5^{2k - 1} \in \mathbb N \implies \dfrac{4^{(k + 1) + 1} + 5^{2(k + 1) - 1}}{21} \in \mathbb N.$

    So the third condition is met for k + 1.

    $\therefore k + 1 \in H.$

    $THUS, H = \mathbb N.$
    Thanks from mathman11 and topsquark
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Jun 2014
    From
    In ah House
    Posts
    75
    Thanks
    2

    Re: induction help

    thanks for the help folks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Using induction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 14th 2011, 08:31 AM
  2. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. Induction
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: March 12th 2010, 05:35 PM
  5. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM

Search Tags


/mathhelpforum @mathhelpforum