<s>[INST] 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.
 [/INST] 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
</s>