# Prove by Induction

1. Nov 12, 2013

### lionely

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. Nov 12, 2013

### haruspex

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.

3. Nov 12, 2013

### lionely

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.

4. Nov 12, 2013

### lionely

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?

5. Nov 12, 2013

### haruspex

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.

6. Nov 12, 2013

### lionely

So... put Un in the recurrence relation, and just simplify it until it looks like

$U_n = \frac 12(1-2^{-2^n+1})$ ?

7. Nov 12, 2013

### haruspex

Not quite. You need it to look like $U_{n+1} = \frac 12(1-2^{-2^{n+1}})$. Note both differences from your version.

8. Nov 12, 2013

### lionely

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.

9. Nov 12, 2013

### Ray Vickson

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.

10. Nov 12, 2013

### lionely

1/2 (1-2^(-2^n)) (2^(2-2^n)+1) . I am stuck and this is what I ended up with.

11. Nov 12, 2013

### haruspex

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.

12. Nov 12, 2013

### lionely

I expanded (1-2^(-2^n)) (1/2+2^(-2^n+1)) and got something quite confusing so I tried factoring out a half.

13. Nov 12, 2013

### haruspex

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.

14. Nov 12, 2013

### lionely

$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?

15. Nov 12, 2013

### haruspex

Sign error.

16. Nov 12, 2013

### lionely

$(1-2^{-2^n})(\frac 12 + \frac12 2^{-2^n}))$

so try to expand and simplify this?

17. Nov 12, 2013

### haruspex

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.

18. Nov 12, 2013

### lionely

oh it's a difference of two squares. Thanks I got the answer now.