Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: I think of it as hard proof by induction

  1. May 30, 2008 #1

    rock.freak667

    User Avatar
    Homework Helper

    [SOLVED] I think of it as hard proof by induction

    1. The problem statement, all variables and given/known data

    given for the sequence [itex]a_1,a_2,a_3,a_4,...[/itex],[itex]a_1=1[/itex] and that

    [tex]a_{n+1}=(a_n+\frac{1}{a_n})^{\lambda}[/tex]

    where[itex]\lambda>1[/itex].Prove by mathematical induction that,for [itex]n \geq 2[/itex]

    [tex]a_n \geq 2^{g(n)}[/tex]

    where [itex]g(n)=\lambda^{n-1}[/itex]

    Prove also,for [itex]n \geq 2[/itex]

    [tex]\frac{a_{n+1}}{a_n}>2^{(\lambda -1)g(n)}[/tex]
    2. Relevant equations



    3. The attempt at a solution

    well what I tried to do was to consider [itex]a_{n+1}-2^{g(n)}[/itex]

    which after simplification gives:

    [tex] \frac{(a_n^2+1)^{\lambda}}{a_n^{\lambda}}-2^{g(n)}[/itex]

    which I then said should be greater than or equal to zero since the fraction on the left is +ve and 2^g(n) is positive since lambda is >1. Is this a good way to start?
     
  2. jcsd
  3. May 30, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Not really. I think you are supposed to use induction. Prove the statement is true for n=1. Then prove is the statement is true for n, then it's true for n+1. Isn't that how induction is supposed to go? What you've done so far doesn't look very 'inductive'.
     
  4. May 30, 2008 #3

    rock.freak667

    User Avatar
    Homework Helper

    Well what I was essentially trying to do was to find an expression for a_n+1-2^g(n) and then add,subtract,multiply and divide various things to [itex]a_n \geq 2^{g(n)}[/itex] and then eventually say that from my expression a_n+1 >= 2^g(n)
     
  5. May 30, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, I know. But the problem says 'use induction'. And that might be the best way to go. I'll warn you, I haven't actually tried to do it.
     
  6. May 30, 2008 #5

    exk

    User Avatar

    As Dick mentioned induction may be the way to go:

    [tex]a_2=2^{\lambda}[/tex]

    Take your expression now and show that the statement is true for n=2 (I guess this is also your inductive hypothesis):

    [tex]
    \frac{(a_n^2+1)^{\lambda}}{a_n^{\lambda}}-2^{g(n)} \geq 0 --> \frac{(a_n^2+1)}{a_n} \geq 2^{\lambda^{n-2}}
    [/tex]

    So then:
    [tex]\frac{(a_2^2+1)}{a_2} \geq 2 --> \frac{(2^{2\lambda}+1)}{2^{\lambda}} \geq 2 [/tex]

    So now you need to find a way to express the relation for n=k+1. I guess expanding a couple of terms may be helpful, but I always came back to the general form that you proposed.
     
  7. May 30, 2008 #6

    rock.freak667

    User Avatar
    Homework Helper

    Then just say:

    Assume true for n=N

    [itex]a_N \geq 2^{g(n)}[/itex]

    + [itex]\frac{1}{a_N}[/itex]

    [tex]a_N +\frac{1}{a_N} \geq 2^{g(n)} +\frac{1}{a_N}[/tex]


    Raise both sides to the power of [itex]\lambda[/itex]


    [tex](a_N +\frac{1}{a_N})^{\lambda} \geq (2^{g(n)} +\frac{1}{a_N})^{\lambda}[/tex]

    and then say that

    [tex](2^{g(n)} +\frac{1}{a_N})^{\lambda} \geq 2^{g(N+1)}[/tex]

    and so

    [tex]a_{N+1}>2^{g(N+1)}[/tex]

    and hence true by PMI ?
     
  8. May 30, 2008 #7

    Vid

    User Avatar

    We need to show that

    (an + 1/an)^t >= 2^(t^(n))
    Observation:
    t*ln(an + 1/an) >=t^(n)ln(2)
    ln(an + 1/an) >= t^(n-1)(ln(2))
    an + 1/an >= 2^(t^(n-1))
    Since t >= 1, it's an increasing sequence. Thus,
    an + 1/an > an >= 2^(t^(n-1)) by the inductive hypothesis. QED.
     
  9. May 30, 2008 #8

    Vid

    User Avatar

    I see no problems with your proof.
     
  10. May 31, 2008 #9

    rock.freak667

    User Avatar
    Homework Helper

    hm.didn't think about taking ln...interesting

    But I might need to justify why

    [tex](2^{g(n)} +\frac{1}{a_N})^{\lambda} \geq 2^{g(N+1)}[/tex]

    so I would just say that the 2^g(n)+(anything) must be bigger than 2^(g(n+1)) since a_n is greater than zero
     
  11. May 31, 2008 #10

    Vid

    User Avatar

    (2^(t^(n-1) + 1/an)^t >= 2^(t^(n-1)*t) = 2^(t^n) = 2^(g(n+1)). The inequality holds since t> 1 and an is postive.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook