Time Complexity recurrence

Question

When we have the recurrence $T(N)=T(N-1)+T(N-2)$, one normally uses $x^N$ and solves for $x$ which gives the golden ratio. But why does one use $x^N$ and not something else, like $\log(N)$ or $N$?

Answer 1

We can "factor" a linear equation with constant coefficients, i.e. transform it to a cascade of first order equations.

Consider the second order equation

$$T_n+rT_{n-1}+sT_{n-2}=0$$ which we rewrite as $$T_n-(a+b)T_{n-1}+abT_{n-2}=0.$$

Then, let us define an intermediate sequence $R$ such that

$$R_n=T_n-aT_{n-1}.$$

From the definition we have

$$R_n-bR_{n-1}=T_n-aT_{n-1}-b(T_{n-1}-aT_{n-2})=T_n-(a+b)T_{n-1}+abT_{n-2}=0.$$

The solution of $$\color{green}{R_n-bR_{n-1}=0}$$ is obviously of the form $$\color{green}{R_n=bR_{n-1}=b^2R_{n-2}=b^3R_{n-3}=\cdots=b^nR_0=cb^n}.$$ (This is where the powers are coming from.)

Then we solve

$$T_n-aT_{n-1}=cb^n,$$

which will be the sum of the general solution of the homogeneous equation

$$T_n-aT_{n-1}=0$$ i.e. $$T_n=c'a^n,$$ and a particular solution of the non-homogeneous equation which can be

$$c''b^n.$$

Indeed,

$$T_n-aT_{n-1}=c''b^n-ac''b^{n-1}=c''(1-\frac ab)b^n=cb^n.$$

Hence,

$$T_n=c'a^n+c''b^n.$$

The method extends to equations of any order and one can show that the solution is a linear combination of the $n$-th powers of the roots of the so-called characteristic polynomial (the polynomial obtained by replacing $T_{n+k-d}$ by $x^k$; in the above case, $x^2+rx+s$).

To summarize, the terms $a^n$ come form the solution of some first order homogeneous equation $T_n=aT_{n-1}$.

---

Note that when the characteristic polynomial has multiple roots, the powers $a^n$ aren't sufficient, and you need to consider terms of the form $n^ma^n$.

You may also find roots which are complex, and you will need terms like $r^n\cos(n\theta)$ and $r^n\sin(n\theta)$.