0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

"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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.