Solution to sequence defined by $s_1=11$ and $s_{n+1}=\frac{2}{3}(s_n+5)$ that almost works, but I don't understand

Question

This is an add on to the question I asked at Finding formulas for the terms in a recursion defined by $s_1 = 11$ and $s_{n+1}=\frac23(s_n+5)$ . The solutions given in the answers started with the finding the sum equations for the system, then determining their change function by subtracting the sums. I am looking for an answer that will use will find the change function without first finding the equation for the sums. I am close, but I am not sure exactly why my method is working and I need to fudge some numbers to get it to work properly. I would like to have some insight into this method.

So you have the following system of equations:

$$\begin{align}s_1 &= 11 \\[4pt] s_{n+1} &= \frac23 ( s_n + 5 ) \end{align}$$

Let $f_{n+1}$ be the change function. Therefore:

$$\begin{gather} f_{n+1} = \frac{2}{3}(s_n + 5) - s_n \\[4pt] 3f_{n+1} = 2s_n + 10 - 3s_n \\ 3f_{n+1} = -s_n + 10\\ 3f_{n+1} = -\sum_{i=1}^n f_i + 10 \\ 3f_{n+1} = -\sum_{i=2}^n f_i - 11 + 10 \\ 3f_{n+1} + 1 = -\sum_{i=2}^n f_i \end{gather}$$

Now here is where the magic happens. I came across bkarpuz's post at How do you solve a recurrence with a summation function inside , and applied it to my equation.

$$\begin{align}3 * \lambda^{n+1} + \lambda^n = -\lambda^n \\[4pt] \lambda = -2/3 \end{align}$$

This implies that the function will be in the form $c*(-2/3)^n$ and we can find $c$ just by plugging in an initial value. But this is only close. The actual formula is:

$$\begin{align}f_{n+1} = -(1/3)*(2/3)^{n-1} \\[4pt] \end{align}$$

Could you please shed some light on why this method gets us close, and answer why it is giving $(-2/3)$ instead of $(2/3)$.

Answer 1

Your problem with the bkarpuz post is that he didn't explicitly write out a step, so you skipped it entirely. Applied to your problem, the step would read: $$3f_{n+1}+1=-\sum_{i=2}^nf_i$$ $$3f_{n+2}+1=-\sum_{i=2}^{n+1}f_i$$ Now on subtracting the first equation above from the second we find $$3f_{n+2}-3f_{n+1}=-f_{n+1}$$ So $$3f_{n+2}-2f_{n+1}=0$$ So this is the difference equation that bkarpuz is solving (but now appropriate to your problem)! If we now let $f_n=c\lambda^n$, then $$c\left(3\lambda^{n+2}-2\lambda^{n+1}\right)=3c\lambda^{n+1}\left(\lambda-\frac23\right)=0$$ Since not all of the $f_{n+1}$ can be zero, it follows that $\lambda=2/3$. Then $$f_2=s_2-s_1=\frac{32}3-11=-\frac13=c\left(\frac23\right)^2$$ So $$c=-\frac13\left(\frac32\right)^2$$ and $$s_{n+1}-s_n=f_{n+1}=-\frac13\left(\frac32\right)^2\left(\frac23\right)^{n+1}=-\frac13\left(\frac23\right)^{n-1}$$

Answer 2

It's better if you don't treat it as magic. :-)

Your recurrence, for $n \geq 1$, is

$$ 3f_{n+1}+1 = -\sum_{i=2}^n f_i $$

Note that your original post has an error: The summand in the RHS should be $f_i$, not $f_n$. Define $F(z)$ to be the probability generating function for $f_i$:

$$ F(z) = \sum_{i=1}^\infty f_iz^i $$

We will attempt to solve for $F(z)$, using the recurrence equation. That equation is true for $n = 1, 2, 3, \ldots$ without end. Let's multiply the $n$th equation by $z^n$:

$$ 3z^nf_{n+1}+z^n = -z^n\sum_{i=2}^n f_i $$

Now, we'll sum all of the equations:

$$ \sum_{n=1}^\infty 3z^nf_{n+1}+\sum_{n=1}^\infty z^n = -\sum_{n=1}^\infty z^n \sum_{i=2}^n f_i $$

Reorder the RHS, recognizing that we have an empty sum when $n = 1$, and that $f_i$ doesn't depend on $n$:

$$ \sum_{n=1}^\infty 3z^nf_{n+1}+\sum_{n=1}^\infty z^n = -\sum_{i=2}^\infty f_i \sum_{n=i}^\infty z^n $$

Pull a factor of $3/z$ out of the leftmost sum, and evaluate the rightmost sum:

$$ \frac3z\sum_{n=1}^\infty z^{n+1}f_{n+1}+\sum_{n=1}^\infty z^n = -\sum_{i=2}^\infty f_i \frac{z^i}{1-z} $$

Adjust the index on the leftmost sum, evaluate the second sum, and pull out a factor of $1/(1-z)$ from the rightmost sum:

$$ \frac3z\sum_{n=2}^\infty z^nf_n+\frac{z}{1-z} = -\frac{1}{1-z}\sum_{i=2}^\infty f_i z^i $$

We now recognize in two places a close approximation to $F(z)$, except that we're missing $f_1$ in both cases. Define $G(z) = F(z)-f_1$, and we have

$$ \frac3z G(z)+\frac{z}{1-z} = -\frac{1}{1-z}G(z) $$

Multiplying by $z(1-z)$ (we'll ignore the constant sequence for now) yields

$$ 3(1-z)G(z)+z^2 = -zG(z) $$

Solve for $G(z)$ to get

$$ G(z) = -\frac{z^2}{3-2z} = \frac{-\frac13 z^2}{1-\frac23 z} $$

You will perhaps recognize this as equal to the geometric series

$$ G(z) = -\frac13 z^2 -\frac29 z^3 -\frac{4}{27} z^4 - \cdots -\frac13\left(\frac23\right)^n z^{n+2} -\cdots $$

One can read off the $g_n = f_n$ from this expression for all $n \geq 2$; to this must merely be added $f_1 = 11$.

Answer 3

Your equation for $s_n$ is linear, make the Ansatz

$$s_n=q^n$$ and compute $q$ the solution for $s_n$ is given by $$s_n=C_1q_1+C_2q_2$$ for your Control, the solution is given by $$s_n=\frac{1}{2} 3^{-n} \left(3\ 2^n+20\ 3^n\right)$$