1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Kendall
    Nov 23, 2021 at 19:30

1 Answer 1

3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .