1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove by Induction

  1. Nov 12, 2013 #1
    1. The problem statement, all variables and given/known data

    The sequence {Un} is defined by the recurrence relation

    Un+1 = 2Un(1-Un), n≥0, U0 = 1/4

    Prove by Induction that

    Un = 1/2( 1 - 1/22^n )


    I'm sorry I didn't know how to type this any better the 2 is raised to the power of 2 and that 2 is raised to the power of n




    3. The attempt at a solution

    I'm confused, to prove this by induction won't I just need to put in n+1? If I put in n+1 it looks finished to me, I don't need to rearrange it to look a certain way... so putting n+1 in Un has proved it? Please guide me !
     
  2. jcsd
  3. Nov 12, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Proof by induction is in two parts:
    1. Assume the formula is correct up to some n. You cannot then simply substitute n+1 for n, since you're not assuming it's true for n+1 - that is what you need to prove. So use the formula with n and the recurrence relation to prove that the formula is also true at n+1.
    2. You need to start the induction by showing it is true for some n = N0. Then you know it is true for all larger n.
     
  4. Nov 12, 2013 #3
    Well I forgot to type I started off by Using Un for n=1 and 2 but I didn't use the recurrence relation because I was confused, as to why it was given to me when I could just use Un... but I'll try to use the recurrence relation then.
     
  5. Nov 12, 2013 #4
    But I'm confused now I should have Un+1 = 2Un(1-Un)

    substituting Un and I think Un+1 is equal to Un to n+1th term right?
    so

    1/2(1- 1/2^2^n) + (n+1) = (1- 1/2^2^n) (1- [1-1/2^n^n])

    Does this make sense?
     
  6. Nov 12, 2013 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You know ##U_{n+1} = 2 U_n(1-U_n)## and ##U_n = \frac 12(1-2^{-2^n})##.
    Use the second to substitute for Un in the first.
    You need to deduce that the solution also works for Un+1.
     
  7. Nov 12, 2013 #6
    So... put Un in the recurrence relation, and just simplify it until it looks like

    ##U_n = \frac 12(1-2^{-2^n+1})## ?
     
  8. Nov 12, 2013 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Not quite. You need it to look like ##U_{n+1} = \frac 12(1-2^{-2^{n+1}})##. Note both differences from your version.
     
  9. Nov 12, 2013 #8
    lol I meant to have the +1 up there but I'm not really familiar with the itex format if it's called that. I just copied yours and put the +1 . But Okay I think I get it now, I'll try to juggle it until it comes down to that. Thank you.
     
  10. Nov 12, 2013 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You don't need to use LaTeX/TeX; you can use parentheses instead, so the proposed value of u_{n+1} in plain text is (1/2)[1 - 2^(-2^(n+1))]. That is perfectly understandable and unambiguous.
     
  11. Nov 12, 2013 #10
    1/2 (1-2^(-2^n)) (2^(2-2^n)+1) . I am stuck and this is what I ended up with.
     
  12. Nov 12, 2013 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Pace Ray, but I find that hard to read, so I'll write it in LaTex: ##\frac 12 (1-2^{-2^n}) (2^{2-2^n}+1)##
    I don't see where the first 2 in 2-2n comes from.
     
  13. Nov 12, 2013 #12
    I expanded (1-2^(-2^n)) (1/2+2^(-2^n+1)) and got something quite confusing so I tried factoring out a half.
     
  14. Nov 12, 2013 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    In LaTex again:
    ##(1-2^{-2^n}) (\frac 12+2^{-2^{n+1}}) ##
    It's confusing because it's wrong. Start again from ##2U_n(1-U_n) = 2 (\frac 12(1-2^{-2^n}))(1-\frac 12(1-2^{-2^n}))##. Simplify the second half first. If still a problem, pls post intermediate steps so we can see where the error is.
     
  15. Nov 12, 2013 #14
    ##2 (\frac 12(1-2^{-2^n}))(1-\frac 12(1-2^{-2^n}))##

    = ##2 (\frac 12(1-2^{-2^n}))(\frac 12-\frac12 2^{-2^n}))##

    = ##(1-2^{-2^n})(\frac 12-\frac12 2^{-2^n}))##

    So should I now expand this?
     
  16. Nov 12, 2013 #15

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Sign error.
     
  17. Nov 12, 2013 #16
    ##(1-2^{-2^n})(\frac 12 + \frac12 2^{-2^n}))##

    so try to expand and simplify this?
     
  18. Nov 12, 2013 #17

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes. If you rewrite as ##\frac 12(1-2^{-2^n})(1+ 2^{-2^n}))## you might notice something interesting which will make expansion a little easier.
     
  19. Nov 12, 2013 #18
    oh it's a difference of two squares. Thanks I got the answer now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove by Induction
  1. Proving by induction (Replies: 1)

  2. Prove by Induction (Replies: 2)

  3. Prove by induction (Replies: 5)

Loading...