Prove by Induction: Un = 1/2(1 - 1/22^n)

[lionely]

Homework Statement

The sequence {Un} is defined by the recurrence relation

U_n+1 = 2Un(1-Un), n≥0, U₀ = 1/4

Prove by Induction that

Un = 1/2( 1 - 1/2²^ⁿ )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

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 !

 

[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.

 

[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.

 

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

 

[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 U_n in the first.
You need to deduce that the solution also works for U_n+1.

 

[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})$ ?

 

[haruspex]

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

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

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

 

[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.

 

[Ray Vickson]

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.

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.

 

[lionely]

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

 

[haruspex]

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

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-2ⁿ comes from.

 

[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.

 

[haruspex]

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

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.

 

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

 

[haruspex]

$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}))$

Sign error.

 

[lionely]

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

so try to expand and simplify this?

 

[haruspex]

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

so try to expand and simplify this?

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.

 

[lionely]

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