# Can a recurrence relation have more than one exact solution?

Can a homogeneous linear second degree relations with constant coefficients have more than one exact solution?

Consider the following $T(n) + aT(n - 1) + bT (n - 2) = 0$

Some equations of this form have a general solution of the form: $T(n) = c_1r^n + c_2nr^n$

Can a relation have more than one general solution?

## 3 Answers

You would expect this equation to have two linearly independent solutions. Once you specify two starting conditions, there is a unique solution. Given $T(n)+aT(n-1)+bT(n-2)$, as you say the solutions are $T_1(n)=c_1r_1^n, T_2(n)=c_2r_2^n$ where $r_1, r_2$ are the roots of $r^2+ar+b=0$. There is a perturbation if the roots are not distinct. As the equation is linear and homogenous, the solutions form a two dimensional vector space. Once you specify $T(0), T(1)$, you can solve two equations in two unknowns to get $c_1,c_2$ and you have a unique solution.

No--The whole point of a general solution is that it's general. Suppose you have two separate general solutions, $T'(n)$ and $T''(n)$. Let $T'''(n) = c_1 T'(n) + c_2 T''(n)$ for some real numbers $c_1$ and $c_2$. Then \begin{align}&T'''(n) + aT'''(n-1) + bT(n-2) \\ = &\left[c_1 T'(n) + c_2 T''(n)\right] + a\left[c_1 T'(n-1) + c_2 T''(n-1)\right] + b\left[c_1 T'(n-2) + c_2 T''(n-2)\right] \\ = & c_1\left[ T'(n) + aT'(n-1) + bT'(n-2)\right] + c_2\left[T''(n) + aT''(n-1) + bT''(n-2)\right] \\ = & c_1\times0 + c_2\times 0\\ = & 0. \end{align} So $T'''(n)$ is a general solution that includes both $T'(n)$ and $T''(n)$ as special cases.

An equation of the form $$T(n)-(\alpha+\beta)T(n-1)+\alpha\beta T(n-2)=0 \text { with }\alpha \neq \beta$$ has a general solution of the form $$T(n)=A\alpha^n+B\beta^n$$

$A$ and $B$ can be determined from two values of $T(n)$ eg $T(0)$ and $T(1)$ - this makes sense because two values completely determine the solution of the recurrence simply by successive applications of the recurrence equation.

When $\alpha = \beta$ there are still two degrees of freedom in the solution, but now the form is $$T(n)=(An+B)\alpha^n$$

This last case is best seen using the generating function $$g(t)=\sum_{n=0}^\infty T(n)t^n$$ from which we obtain $$(1-2\alpha t+\alpha^2t^2)g(t)=T(0)+(T(1)-2\alpha T(0))t=P+Qt$$

We then have - using partial fraction decomposition $$g(t)=\frac{P+Qt}{(1-\alpha t)^2} = \frac {R}{1-\alpha t}+\frac {S}{(1-\alpha t)^2}$$

If we expand these expressions using the binomial theorem, we can obtain $T(n)$ in the form I suggested. Once the form is known, it can be applied directly to the problem. Similar calculations prove the forms for triple and higher roots in linear recurrences with more terms. (If the roots are distinct, the partial fractions are all of the form $\frac A {1-\alpha t}$ for the various roots.)