How do I use trend spotting to find a closed form for a recursive sequence?

Question

In this problem I am given a recursive equation: $$u_{n+1} = 2 + 3u_n$$

I am also given the value $u_1 = 1$.

From this information, I created a data table with $n$ and $u_n$, respectively.

My Values: $$ \begin{array}{c|c} n & u_n \\ \hline 1 & 1 \\ 2 & 5 \\ 3 & 17 \\ 4 & 53 \\ 5 & 161 \\ \end{array} $$

I am supposed to derived a closed form of the equation from this list of data. I haven't found a way of doing this, and wonder if there is some sort of trick? It has become apparent to me that trend spotting is not exactly my strong suit so some reference to that would be greatly appreciated.

Answer 1

Hint:

From your table, it looks like $u_n$ is always odd, so $u_n + 1$ is even. What does it look like $\frac{u_n + 1}{2}$ is?

Answer 2

We are given $$ u_{n+1}=2+3u_n\tag{1} $$ Divide $(1)$ by $3^{n+1}$: $$ \frac{u_{n+1}}{3^{n+1}}=\frac2{3^{n+1}}+\frac{u_n}{3^n}\tag{2} $$ Induction yields $$ \begin{align} \frac{u_n}{3^n} &=u_0+\sum_{k=1}^n\frac2{3^k}\\ &=u_0+\frac23\frac{1-\frac1{3^n}}{1-\frac13}\\ &=u_0+1-\frac1{3^n}\tag{3} \end{align} $$ Multiply $(3)$ by $3^n$ $$ \begin{align} u_n &=3^n(u_0+1)-1\\ &=2\cdot3^{n-1}-1\tag{4} \end{align} $$ where $u_0=-\frac13$.

Answer 3

Generalize: consider the recursion $u_{n+1} = a + b u_{n}$, and for the moment disregard the initial value.

Generalize even more: this is of the form $L[U] = B$, where $L$ is a linear operator on sequences. So the general solution should be of the form $U = S + t V $ for arbitrary constant $t$, where $S$ is a particular solution and $V$ is a solution of the homogeneous equation $L[U] = 0$.

In this case the homogeneous equation would be $u_{n+1} = b u_n$, and it's easy so see $u_n = b^n$ is a solution of that.

For a particular solution, you might try a constant: $c$ such that $c = a + b c$. As long as $b \ne 0$, you can solve this.

So now your general solution is of the form $u_n = c + t b^n$ (with the appropriate value of $c$), and you just have to find $t$ to make this work with your initial condition.

Answer 4

Considering $$u_{n+1} = 2 + 3u_n\implies 1+u_{n+1} = 3 + 3u_n=3(1+u_n)$$ Define $v_n=u_n+1$ to get the reccurence relation to be $$v_{n+1}=3v_n$$ from which you easily see that $$v_n=c\, 3^{n-1}\implies u_n=-1+c\, 3^{n-1}$$ Then, if $u_1=a$, then $c=1+a$.