How to Find Characteristic Equations?

I try to find the characteristic equations of given recurrences. My textbook finds it magically without doing a calculation but I don't understand how to do that. I write 1 page of equations to find the characteristic equation. Is there an easier way to find it?

Ex.

T(n) = 2T($$\frac{n}{2}$$) + n + $$\log_2 n$$

(n = $$2^k$$)

CE = $$(x-2)^2(x-1)^2$$

How to find the CE without any calculation (That's what my textbook does)? Is it possible?

• You can sometimes eyeball Homogeneous Recurrence Relation solutions or CEs but I doubt it's possible with non-homogeneous cases. It's most likely just giving you a solution for reference. The calculation is not that lengthy though. Nov 23, 2021 at 19:30

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