Results 1 to 5 of 5

Thread: Prove using induction

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

    Prove using induction

    Let $\displaystyle a_1=5$, and let $\displaystyle a_{n+1}=a_n^2$. Prove that the last n digits of $\displaystyle a_n$ are the same as the last n digits of $\displaystyle 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 $\displaystyle a_{n+1} - a_n $ using the formula $\displaystyle x^2 - y^2 = (x+y)(x-y) $ and show that $\displaystyle 10^n $ divides it.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Prove using induction

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

    $\displaystyle =a_n(a_n-1)$

    $\displaystyle =5^{2^{n-1}}(5^{2^{n-1}}-1)$

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

    $\displaystyle 5^n | 5^{2^{n-1}}(5^{2^{n-1}}-1)$

    How do I show that $\displaystyle 2^n | (5^{2^{n-1}}-1)$?
    Last edited by alexmahone; Aug 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
    $\displaystyle a_{n+1}-a_n=a_n^2-a_n$

    $\displaystyle =a_n(a_n-1)$

    $\displaystyle =5^{2^{n-1}}(5^{2^{n-1}}-1)$

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

    $\displaystyle 5^n | 5^{2^{n-1}}(5^{2^{n-1}}-1)$

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


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

    In particular, $\displaystyle 2^{n+1}|5^{2^{n-1}}-1$ and therefore $\displaystyle 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,111
    Thanks
    7

    Re: Prove using induction

    I just got it!!

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

    $\displaystyle 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.

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

    $\displaystyle a_{n+2}-a_{n+1}=a_{n+1}^2-a_{n+1}$

    $\displaystyle =a_n^4-a_n^2$

    $\displaystyle =(a_n^2-a_n)(a_n^2+a_n)$

    $\displaystyle a_n^2-a_n$ is divisible by $\displaystyle 10^n$.

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

    So, $\displaystyle (a_n^2-a_n)(a_n^2+a_n)=a_{n+2}-a_{n+1}$ is divisible by $\displaystyle 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: Jan 11th 2012, 02:12 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. Prove each of the following by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 25th 2010, 10:45 AM
  4. Prove induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Nov 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