Deriving a recurrence equation

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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