How to Find Characteristic Equations?

Solution 1:

Define $A(n)=T(2^n)$ and $S$ to be the shift operator: $S(A)(n)=A(n+1)$. Your equation is $2^n+n=A(n)-2A(n-1)=(S-2)A(n-1)$. If $P(S)$ is a polynomial in $S$ with constant coefficients such that $P(S)(2^n+n)=0$, then $$(S-2)P(n)A(n-1)=0$$ The characteristic polynomial of this linear recurrence is $(x-2)P(x)$.

So, what we need is an efficient algorithm to compute a small polynomial operator $P(S)$ that annihilates $2^n+n$.

You can see that $S-2$ annihilates $2^n$, since $(S-2)(2^n)=2^{n+1}-2\cdot 2^n=0$.

Also, $(S-1)^2$ annihilates $n$, since $(S-1)n=n+1-n=1$ and $(S-1)1=1-1=0$.

Therefore, the polynomial $P(S)=(S-2)(S-1)^2$ annihilates $2^n+n$ and then $$(S-2)^2(S-1)^2A(n-1)=0$$

In general, polynomials $P(S)$ that annihilate expressions that are sum of terms of the form $Cn^ka^n$, with $C,a$ constants, are easy to find by inspection. You can verify that $P(S)=(S-a)^{k+1}$ annihilates $Cn^ka^n$. In fact $(S-a)(Cn^ka^n)=C(n+1)^kaa^n-Can^ka^n$, which is $a^n$ multiplied by a polynomial of degree $k-1$ in $n$. Since $(S-a)a^n=a^{n+1}-a^{n+1}=0$, we get the result by induction. So, for a sum of many of those terms, you can just take the product, or better the least common multiple.

Example: $n^2+3n3^n+1=n^2\cdot 1^n+3n^13^n+n^01^n$ is of the form above. We have that $(S-1)^3$ annihilates $n^21^n$, $(S-3)^2$ annihilates $3n^13^n$ and $(S-1)$ annihilates $1$. Therefore, their least common multiple $(S-1)^3(S-3)^2$ annihilates $n^2+3n3^n+1$.