Results 1 to 5 of 5

Math Help - Prove using induction

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Prove using induction

    Let a_1=5, and let a_{n+1}=a_n^2. Prove that the last n digits of a_n are the same as the last n digits of a_{n+1}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162

    Re: Prove using induction

    Find the general term for the sequence, factorize the difference  a_{n+1} - a_n using the formula  x^2 - y^2 = (x+y)(x-y) and show that 10^n divides it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Prove using induction

    Quote Originally Posted by Traveller View Post
    Find the general term for the sequence, factorize the difference  a_{n+1} - a_n using the formula  x^2 - y^2 = (x+y)(x-y) and show that 10^n divides it.
    a_{n+1}-a_n=a_n^2-a_n

    =a_n(a_n-1)

    =5^{2^{n-1}}(5^{2^{n-1}}-1)

    Since 2^{n-1} \geq n,

    5^n | 5^{2^{n-1}}(5^{2^{n-1}}-1)

    How do I show that 2^n | (5^{2^{n-1}}-1)?
    Last edited by alexmahone; August 13th 2011 at 07:55 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Re: Prove using induction

    Quote Originally Posted by alexmahone View Post
    a_{n+1}-a_n=a_n^2-a_n

    =a_n(a_n-1)

    =5^{2^{n-1}}(5^{2^{n-1}}-1)

    Since 2^{n-1} \geq n,

    5^n | 5^{2^{n-1}}(5^{2^{n-1}}-1)

    How do I show that 2^n | (5^{2^{n-1}}-1)?
    You may be familiar with the result that says: If a is odd, then 2^{n+2}|a^{2^n}-1 for n\geq1.


    The main part of the proof by induction on n is:
    Suppose for some n\geq1 it's true that 2^{n+2}|a^{2^n}-1. Then look at a^{2^{n+1}}-1=(a^{2^n}-1)(a^{2^n}+1).

    In particular, 2^{n+1}|5^{2^{n-1}}-1 and therefore 2^n|5^{2^{n-1}}-1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Prove using induction

    I just got it!!

    We need to prove that a_{n+1}-a_n is divisible by 10^n.

    a_2-a_1=25-5=20, which is divisible by 10.

    So, the statement is true for n = 1.

    Let the statement be true for n.

    a_{n+1}-a_n=a_n^2-a_n is divisible by 10^n.

    a_{n+2}-a_{n+1}=a_{n+1}^2-a_{n+1}

    =a_n^4-a_n^2

    =(a_n^2-a_n)(a_n^2+a_n)

    a_n^2-a_n is divisible by 10^n.

    a_n^2+a_n=a_{n+1}+a_n is divisible by 10. (As both a_{n+1} and a_n end with 5.)

    So, (a_n^2-a_n)(a_n^2+a_n)=a_{n+2}-a_{n+1} is divisible by 10^{n+1}. This completes the proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Use Induction to prove
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: January 11th 2012, 02:12 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Prove each of the following by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 25th 2010, 10:45 AM
  4. Prove induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 23rd 2008, 07:05 AM
  5. Prove by Induction
    Posted in the Algebra Forum
    Replies: 5
    Last Post: May 30th 2008, 11:16 AM

Search Tags


/mathhelpforum @mathhelpforum