Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - Prove using induction on n that 3 divides (4^n)+5

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    9

    [Solved] Prove using induction on n that 3 divides (4^n)+5

    Hi everyone,

    First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.

    Question: Prove by induction on n that, for all positive integers n, 3 divides 4^n +5.

    I know where I need to go with this, I think, I'm just stuck on the inductive step:

    Proof: We use induction on n. If 3 divides 4^n +5, then 4^n +5=3q for some integer q.

    Base case: If n=1, then 4^n +5=9=3q, where q=3, proving the base case.

    Inductive step: Suppose as inductive hypothesis that 4^k +5=3q for some integer k. Then 4^{k+1} +5=3q (by inductive hypothesis).

    That's as far as I get. Obviously, 4^{k+1} +5=4*4^k +5 by definition, but I get stuck there.

    Thanx in advanx!

    EDIT: not sure how to add the solved prefix, hope this is an okay ad hoc measure.
    Last edited by TimM; July 1st 2011 at 11:01 AM. Reason: solved
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1

    Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by TimM View Post
    Hi everyone,

    First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.
    Question: Prove by induction on n that, for all positive integers n, 3 divides 4^n +5.
    I know where I need to go with this, I think, I'm just stuck on the inductive step:
    Proof: We use induction on n. If 3 divides 4^n +5, then 4^n +5=3q for some integer q.

    Base case: If n=1, then 4^n +5=9=3q, where q=3, proving the base case.

    Inductive step: Suppose as inductive hypothesis that 4^k +5=3q for some integer k. Then 4^{k+1} +5=3\color{red}x\color{black} (by inductive hypothesis). not 3q as written.
    That's as far as I get. Obviously, 4^{k+1} +5=4*4^k +5 by definition, but I get stuck there.

    Thanx in advanx!
    (4)4^k+5=(3)4^k+4^k+5

    Now if 3 divides 4^k+5

    it will certainly divide (3)4^k+4^k+5

    So if 4^k+5=3q, then (3)4^k+4^k+5=3\left(4^k+q\right)=3x
    Last edited by Archie Meade; July 1st 2011 at 12:44 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,407
    Thanks
    1294

    Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by TimM View Post
    Hi everyone,

    First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.

    Question: Prove by induction on n that, for all positive integers n, 3 divides 4^n +5.

    I know where I need to go with this, I think, I'm just stuck on the inductive step:

    Proof: We use induction on n. If 3 divides 4^n +5, then 4^n +5=3q for some integer q.

    Base case: If n=1, then 4^n +5=9=3q, where q=3, proving the base case.

    Inductive step: Suppose as inductive hypothesis that 4^k +5=3q for some integer k. Then 4^{k+1} +5=3q (by inductive hypothesis).

    That's as far as I get. Obviously, 4^{k+1} +5=4*4^k +5 by definition, but I get stuck there.

    Thanx in advanx!
    You need to show that \displaystyle 4^{k + 1} + 5 = 3r, since \displaystyle q and \displaystyle r would be different.

    Anyway...

    \displaystyle \begin{align*} 4^{k + 1} + 5 &= 4\cdot 4^k + 5 \\ &= 4\cdot 4^k + 20 - 15 \\ &= 4(4^k + 5) - 15 \\ &= 4\cdot 3q - 15 \\ &= 3(4q - 5) \\ &= 3r\textrm{ where }r = 4q - 5\end{align*}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2011
    From
    Islamabad
    Posts
    94

    Re: Prove using induction on n that 3 divides (4^n)+5

    from where you left

    4^(k+1) + 5 = 4 . 4^k + 20 - 15

    = 4[ 4^k + 5 ] - 15

    = 4 (3q) - 15 => 3[ 4q - 5 ]

    which gives required result
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by TimM View Post
    Hi everyone,

    First time poster. This is probably an embarrassingly easy problem. I'm a non-maths student working through an intro to proof book in my spare time and there are problem sets with no solutions. I've got stuck on a couple of problems. This is one of them.

    Question: Prove by induction on n that, for all positive integers n, 3 divides 4^n +5.

    I know where I need to go with this, I think, I'm just stuck on the inductive step:

    Proof: We use induction on n. If 3 divides 4^n +5, then 4^n +5=3q for some integer q.

    Base case: If n=1, then 4^n +5=9=3q, where q=3, proving the base case.

    Inductive step: Suppose as inductive hypothesis that 4^k +5=3q for some integer k. Then 4^{k+1} +5=3q (by inductive hypothesis).

    That's as far as I get. Obviously, 4^{k+1} +5=4*4^k +5 by definition, but I get stuck there.

    Thanx in advanx!
    Without induction:

    4^n + 5=(3+1)^n+5=3t+1+5=3t+6
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2011
    Posts
    9

    Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by Prove It View Post
    You need to show that \displaystyle 4^{k + 1} + 5 = 3r, since \displaystyle q and \displaystyle r would be different.
    Lol, obviously. Sorry.

    Anyway, thanks everyone!
    Last edited by TimM; July 2nd 2011 at 06:34 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Dec 2010
    From
    Tétouan/Morocco
    Posts
    44

    Re: Prove using induction on n that 3 divides (4^n)+5

    Hi !
    without induction : 4\equiv 1[3] so 4^{k}\equiv 1[3] knowing that 5\equiv 2[3] by adding we get the result
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1

    Re: Prove using induction on n that 3 divides (4^n)+5

    I don't see the point of giving non-induction answers to questions that clearly state
    to answer using Proof By Induction.
    Who would answer using a different method if an exam question began
    "Prove, by induction........" ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Dec 2010
    From
    Tétouan/Morocco
    Posts
    44

    Re: Prove using induction on n that 3 divides (4^n)+5

    Hi Archie Meade !
    First of all , i didn't give my solution until the others solved it by induction ! You know what , solving problems with different ways is the best way to be good at maths , this is what my brother (who is by the way a winner of a silver medal in the IMO) used to tell me . Take it or leave it .
    Anyway , thanks for being nice and sorry if i was wrong by giving another (better ? ) solution for the exercise .
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2011
    Posts
    9

    Re: Prove using induction on n that 3 divides (4^n)+5

    Hey Tarask, I don't actually understand your answer. I read,

    4 \equiv 1[3]

    As "4 is defined as 1 * 3", but that doesn't make sense to me.
    Last edited by TimM; July 1st 2011 at 05:42 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Mar 2010
    Posts
    715
    Thanks
    2

    Post Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by Archie Meade View Post
    I don't see the point of giving non-induction answers to questions that clearly state
    to answer using Proof By Induction.
    I think there is nothing wrong feeling generous and giving another way to solve it after the problem had been solved through the required method. I myself have benefited and learned from posts of people doing so in more than one occasion (which isn't surprising, as one of the prime qualities of MHF is that is isn't 'give as dictated' answer service, so to speak). Apologies for the off-topic, of course.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by TimM View Post
    Hey Tarask, I don't actually understand your answer. I read,

    4 \equiv 1[3]

    As "4 is defined as 1 * 3", but that doesn't make sense to me.
    Modular arithmetic - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697

    Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by TimM View Post
    Hey Tarask, I don't actually understand your answer. I read,

    4 \equiv 1[3]

    As "4 is defined as 1 * 3", but that doesn't make sense to me.
    what that notation means is "4 is congruent to 1 modulo 3".

    in other words, the difference between 4 and 1 is a multiple of 3 (they are a multiple of 3 "apart").

    the usefulness of this derives from the fact that if a = r (mod n) and b = s (mod n), then

    a+b = r+s (mod n), and ab = rs (mod n). by convention, r and s are integers between 0 and n-1 (inclusive).

    for example, we have that 4 = 1 (mod 3), and 8 = 2 (mod 3) (8 - 2 = 6, which is a multiple of 3).

    if what i said above is true, than we would expect 12 = 4+8 to be congruent to 1+2 = 3 (mod 3) (which it is, since 12 - 3 = 9

    is a multiple of 3), and 32 = (4)(8) to be congruent to (1)(2) = 2 (mod 3) (again true, since 32 - 2 = 30 is a multiple of 3).

    congruence is transitive (you can "pass it along", like equality), so since 3 is congruent to 0 (mod 3), 12 is likewise congruent to 0 (mod 3).

    in other words, the "remainders" upon division by n of integers, obey many of the same rules as integers do.

    this is helpful when considering divisibility questions, since it reduces greatly the number of possible cases to check

    (with division by 3, we have 3 possible "remainders" 0,1 or 2). technically, we get what is called a quotient ring,

    but the abstract general construction is not necessary to understand this specific case.

    personally, the proof i would give is this:

    given that 4^k + 5 = 3q,

    4^(k+1) + 5 = 4(4^k) + 5 = (3+1)(4^k) + 5

    = 3(4^k) + 4^k + 5 = 3(4^k) + 3q = 3(4^k + q).
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1

    Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by TheCoffeeMachine View Post
    I think there is nothing wrong feeling generous and giving another way to solve it after the problem had been solved through the required method. I myself have benefited and learned from posts of people doing so in more than one occasion (which isn't surprising, as one of the prime qualities of MHF is that is isn't 'give as dictated' answer service, so to speak). Apologies for the off-topic, of course.
    It is recommended MHF policy to stay on topic.
    When a question states to specifically answer in a certain way,
    why not concentrate on the requested method?
    The objective is to master "Proof By Induction".

    You're missing my point entirely.

    The given series is a simple arithmetic series,
    however I personally would not encourage a student to answer the question as worded
    using any other method.
    In an exam, it is of no use to offer an alternative.
    It is good of course to learn other ways,
    but at least if offering an alternative,
    one should let the student know not to offer the alternative in an assessment.
    Last edited by Archie Meade; July 2nd 2011 at 02:01 AM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Prove using induction on n that 3 divides (4^n)+5

    Quote Originally Posted by Archie Meade View Post
    It is recommended MHF policy to stay on topic.
    When a question states to specifically answer in a certain way,
    why not concentrate on the requested method?
    The objective is to master "Proof By Induction".
    Not the solution is matter, but the way to solution.

    In this post for instance the OP (maybe)learned the basics of modular arithmetic. I think it is blessed.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Prove 3 divides two integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 9th 2010, 09:38 AM
  2. Prove that ab divides c.
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 3rd 2010, 09:42 AM
  3. Prove that p divides infinitely many numbers...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 28th 2010, 04:55 PM
  4. Prove that gcd(a,b) divides lcm[a,b]
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 15th 2010, 07:44 PM
  5. prove by induction 6 divides n^3 -n
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 1st 2008, 04:08 AM

Search Tags


/mathhelpforum @mathhelpforum