How do I derive a characteristic equation for this specific recurrence relation?

Question

I have no problems solving recurrence relations with two roots, but I've just encountered one with one root: $c_{n+1} = 3c_{n}+1$ such that $c_{0} = 0$.

In my solving process, I suppose I've gotten as far as finding that $cr^{n+1} = 3cr^n + 1$, if that's correct (I don't know if it is).

So how does this translate into a characteristic equation?

Answer 1

It's been years since I did this, but I thought one first considers the homogenous difference equation

$c_{n+1} - 3c_n = 0$,

whose characteristic equation is

$r - 3 = 0$,

which yields $c_n = a 3^n$ as the solution to the homogeneous equation. Then find a particular solution for the nonhomogeneous equation.

Note that as this a first-order recurrence, there is only one characteristic value.

Answer 2

Hint: Increase the index by $1$ and subtract the resulting equations to get rid of the $+1$.

Answer 3

Hint

From: $$c_{n+1} = 3c_{n}+1$$ $$c_{n+j} = 3c_{n+(j-1)}+1$$ get: $$c_{n+j}-c_{n+1} = 3c_{n+j-1}-3c_{n}$$

Answer 4

"That" is not correct since you are applying to an affine recursion an Ansatz designed to solve linear recursions.

When solving the recursion $c_{n+2}=ac_{n+1}+bc_n$, say, one is looking for solutions $c_n=r^n$. Thus $r$ must solve the characteristic equation $r^2=ar+b$. Conversely, if $r$ and $s$ are the roots of the characteristic equation, one sees that every $c_n=Ar^n+Bs^n$ solves the recursion. Since the solutions form a 2-dimensional vector space, this yields all of them and we are happy.

Applying this technique to the recursion $c_{n+1}=ac_{n}+b$ is absurd since the solutions do not form a 2-dimensional vector space anymore. Solving the analogue $r=a$ of the characteristic equation leads nowhere.

The correct Ansatz in this case is to look for solutions $c_n=Ar^n+B$. Here this leads to $Ar^{n+1}+B=aAr^n+aB+b$, which holds simultaneously for every $n$ when $r=a$ and $B=aB+b$. Thus every $c_n=Aa^n+b/(1-a)$ solves the recursion and, since the solutions form a 1-dimensional vector space, this yields all of them and we are happy.

Once one has seen this at least once, one can try at the onset to linearize each recursion $c_{n+1}=ac_{n}+b$ one meets by considering $x_n=c_n+\lambda$ and looking for some $\lambda$ such that $x_{n+1}=ax_n$. This is the strict analogue of shifting the origin of an affine plane to transform an affine function into a linear one.