Results 1 to 8 of 8

Math Help - proofs by induction

  1. #1
    Member
    Joined
    Aug 2007
    Posts
    96

    proofs by induction

    i know this is a kind of big list, but i'm completely lost as to how to do these sort of things and i can't seem to make sense of the book (i've spent about 2 hours trying to figure it out)
    any help walking me through these would be greatly appreciated

    Prove the following by induction:


    A) For all integers n >= 0, the number 5^(2n) - 3n is a multiple of 11

    B) Any integer n >= 1, 2^(4n-1) ends with an 8

    C) The sum of the cubes of three consecutive positive integers is always a multiple of 9

    D) If x >= 2 is a real number and n >= 1 is an integer, then x^n >= nx

    E) If n >= 3 is an integer, then 5^n > 4^n + 3^n + 2^n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by mistykz View Post
    i
    B) Any integer n >= 1, 2^(4n-1) ends with an 8
    Hint: Show that 2^{4n-1} - 8 is always divisible by 10.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2007
    Posts
    127
    A) Doesn't work. e.g. n=4?

    D) x^n \ge nx

    When x=2 and n=1,  2 \ge 2 Therefore true for n=1.
    Assume it's true for n=k.

     x^k \ge kx

    now for induction, we want to prove that  x^{k+1} \ge k(x+1)
    so here is a standard 'trick' often required for similar questions..

    For n=k

     x^k \ge kx

    Times both sides of the inequality by x...

    x^{k+1} \ge kx^2

    But  kx^2 \ge kx for x > 0

    Add x to both sides.....

     kx^2 + x \ge kx + x

     x(kx+1) \ge (k+1)x

    Since  x^{k+1} \ge kx^2 \ge (k+1)x

    It is implied, therefore, that  x^{k+1} \ge (k+1)x as required.

    Hence if n=k is true, then n=k+1 is true. But since n=1 is true, it implies n=2 is true, which implies n=3 is true...etc. Hence proved by induction.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2007
    Posts
    96
    awesome, thanks! anyone else got any others?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2007
    Posts
    127
    Quote Originally Posted by mistykz View Post
    awesome, thanks! anyone else got any others?
    Can you show your working for any others you've attempted?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2007
    Posts
    96
    well, that's the thing. im stuck as to where to start on any of these. he BRIEFLY flew over the stuff, then tossed this homework in our laps. i just sort of need a little coaxing in the right direction
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2007
    Posts
    127
    Well, this is not what you'd call 'elegant', but it's a proof of sorts...
    Just use the same 'trick' I did for question D.

    E) It's easy to prove that the equation is true for n > 2. So I won't waste time or patronise you by proving that. So assume it is true for n=k. Just deal exclusively with the  5^n>4^n

     5^k>4^k

    multiply each side by 5

     5^{k+1}>20^k

    But for k > 2

     20^k > 4^k

    But 20^k > 16^k

    20^k > 4^{k+1} (Since 4^{k+1} = 4(4^k) = 16^k )

    Therefore it follows that  5^{k+1} > 20^k > 4^{k+1}

    which implies  5^{k+1} > 4^{k+1} as required. Hence if n=k is true, then n=k+1 is true. But since n=1 is true, it implies n=2 is true, which implies n=3 is true...etc.


    Repeat the process for  4^n > 3^n then  3^n > 2^n. If you want more help, I'd more more than willing to provide it - but can you at least try to say anything you don't understand - or better yet, post some working, that would be great.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,802
    Thanks
    691
    Hello, mistykz!

    C) The sum of the cubes of three consecutive positive integers is always a multiple of 9
    Let the three consecutive cubes be: . (n-1)^3,\;n^3,\;(n+1)^3

    We want to show that: . (n-1)^3 + n^3 + (n+1)^3 \:=\:9a .for some integer a.


    Vertify S(1)\!:\;\;(1-1)^3 + (1)^2 + (1+1)^3 \;=\;0^3 + 1^3 + 2^3 \;=\;9 . . . yes!


    Assume S(k)\!:\;\;(k-1)^3 + k^3 + (k+1)^3 \;=\;9a .for an integer a.


    Add -(k-1)^3 + (k+2)^3 to both sides:
    . . (k-1)^3 {\color{blue}\,-\, (k-1)^3} + k^3 + (k+1)^3 {\color{blue}\,+\, (k+2)^3} \;=\;9a {\color{blue}\,-\, (k-1)^3 + (k+2)^3}

    and we have:
    . . k^3\,+\,(k+1)^3\,+\,(k+2)^3 \;=\;9a\,-\,k^3\,+\,3k^2\,-\,3k\,+\,1\,+\,k^3\,+\,6k^2\,+\,12k\,+\,8 \;= \;9a +\,9k^2\,+\,9k\,+\,9


    Therefore: . k^3 + (k+1)^3 + (k+2)^3 \;=\;9(a + k^2 + k + 1) . . . . a multiple of 9

    The induction proof is complete.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proofs by Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2010, 10:11 AM
  2. Induction proofs
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 08:32 PM
  3. proofs by induction
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 28th 2009, 05:29 AM
  4. Induction Proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 5th 2009, 07:11 AM
  5. A couple induction set proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 19th 2009, 01:09 AM

Search Tags


/mathhelpforum @mathhelpforum