0

Given this pattern

$\frac{1}{2},\frac{1}{2}\left(\frac{1}{2}\right)+\frac{1}{2},\frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}\right)+\frac{1}{2}\right)+\frac{1}{2}\dots$

In other words $a_1=\frac{1}{2},a_n=\frac{1}{2}a_{n-1}+\frac{1}{2}$

The formula for $a_n=1-\frac{1}{2^n}$

I know a method to solve it from wikipedia given here

And I can see the pattern if I right out the first few terms of the sequence.

Is there any other way of understanding this recurrence relation intuitively or formally?

johnson
  • 482

3 Answers3

2

$a_n=\dfrac12a_{n-1}+\dfrac 12$

$a_n-1=\dfrac12a_{n-1}-\dfrac 12=\dfrac12(a_{n-1}-1)$

$a_n-1=\dfrac1{2^{n-1}}(a_1-1)=-\dfrac1{2^n}$

$a_n=1-\dfrac1{2^n}$

J. W. Tanner
  • 60,406
1

Given $$a_n=\frac{a_{n-1}+1}{2},$$ write (as you see that it approaches $1$), $$b_n=1-a_n.$$ The recurrence becomes $$b_n=\frac{b_{n-1}}{2},$$ from which we can prove by induction that $$b_n=\frac{b_1}{2^{n-1}}=\frac{1-a_1}{2^{n-1}}=\frac{1}{2^n}.$$ So, you can get $$a_n=1-\frac{1}{2^n}$$ rigorously.

Carl Schildkraut
  • 32,931
1

Intuitively ...

Start with a cup with $1/2$ wine and $1/2$ water. In each step, pour out $1/2$ of the mix and top it up with pure water. You can easily convince yourself that:

  • The amount of water obeys the recurrence relation, i.e. if in step $n-1$ you had the amount $a_{n-1}$ of water, in the next step you have $\frac{1}{2}a_{n-1}$ (half of what you had) plus $\frac12$ (what you've added).
  • The amount of wine in each step halves and so is $\frac{1}{2^n}$.

As at each step the glass is full again (with less and less wine :( ), then $a_n+\frac{1}{2^n}=1$ holds for all $n$, which gives you $a_n=1-\frac{1}{2^n}$.