Deriving a recurrence equation I've really been stuck on this problem for a while. We have the equation: $s_t = (s_{t-1}/2)+3$. I need to show the steps it would take to show this can be written as: $s_t = 2^{-t}(s_0-6) +6$. I figure it has something to do with telescoping but I'm not sure how this would be done.
 A: $$\begin{align}
s_t&=\frac{s_{t-1}}2+3\\
&=\frac{s_{t-2}}4+\frac32+3\\
\cdots\\
&=2^{-t}s_0+3\sum_{k=0}^{t-1}2^{-k}
\end{align}$$
A: This is just a direct approach.  First apply the recursion a couple of times to find a pattern.  Then suppose you apply it $i$ times.  Then substitute $i=t$ to show what it would look like if you applied it all the way.  Bam you're done.
$$\begin{align}
s_t &= \frac{1}{2}s_{t-1}+3 \\
s_t &= \frac{1}{2}\left(\frac{1}{2}s_{t-2}+3\right)+3 \\
&= 2^{-2}s_{t-2}+3\left(\frac{1}{2}+1\right)\\
s_t &= \frac{1}{2}\left(\frac{1}{2}\left(\frac{1}{2}s_{t-3}+3\right)+3\right) + 3 \\
&= 2^{-3} s_{t-3}+3\left(\frac{1}{2^2}+\frac{1}{2}+1\right)\\
&\vdots  \\
&\vdots \\
s_t&=2^{-i} s_{t-i}+3\left(\left(\frac{1}{2}\right)^{i-1}+\left(\frac{1}{2}\right)^{i-2}+ \cdots + \left(\frac{1}{2}\right)^{1} + \left(\frac{1}{2}\right)^{0}\right)\\
&=2^{-i} s_{t-i}+3\left(\frac{1-(\frac{1}{2})^i}{1-\frac{1}{2}}\right)\\
&=2^{-i} s_{t-i}+6\left(1-2^{-i}\right)\\
&=2^{-i} (s_{t-i}-6)+6\\
&\vdots \\ 
s_t&=2^{-t}(s_0-6)+6\\
\end{align}$$
Now just verify with math induction
A: Hint: rewrite it as $\;s_t-6 = \dfrac{1}{2}(s_{t-1}-6)\,$, so $\,s_t-6\,$ is a geometric progression, and telescopes to:
$$
s_t-6 = \dfrac{1}{2^1}(s_{t-1}-6) = \dfrac{1}{2^2}(s_{t-2}-6) = \dfrac{1}{2^3}(s_{t-3}-6) = \ldots
$$
