How to solve $T(n) = 4T(n-1) - 3T(n-2) +1$?

Question

Which method should I use and how can I solve this recurrence to find the complexity (order) of the recurrence relation?

The equation is: $T(n) = 4T(n-1) - 3T(n-2) +1$

Find $O(T(n))$.

Answer 1

We have

$$T(n) - 4T(n-1) + 3T(n-2) = 1. \qquad \cdots (1)$$

We solve it like we solve differential equations, by summing a complementary function $C(n)$ and a particular solution $P(n)$, where $C$ solves the homogeneous equation

$$T(n) - 4T(n-1) + 3T(n-2) = 0, \qquad \cdots (2)$$

and $P$ is any solution to (1).

Can you continue? Do you know what is an eigenfunction to (2)?

The characteristic equation is $x^2-4+3=0$, so $(x-3)(x-1)=0$.

Thus $C(n) = A\cdot 3^n + B\cdot 1^n$, where A and B are constants, to be determined by initial data (such as T(0), T(1)).

Now, we may try to find a particular solution. We usually start by trying constants. However, constants can only solve the homogeneous equation in this case, so we proceed to try linear functions $P(n) = c\cdot n$. According to a helpful commenter Zarrax, we get $ c = -1/2$.

However, you only care about the complexity (order) of the solution. So yeah, clearly the order is $O(3^n)$

Answer 2

$T(n)=4T(n-1)-3T(n-2)+1$

$T(n-1)=4T(n-2)-3T(n-3)+1$

subtract:

$T(n)-T(n-1)=4T(n-1)-7T(n-2)+3T(n-3)$

$T(n)=5T(n-1)-7T(n-2)+3T(n-3)$

Now you have a homogeneous recurrence relation. Do you know how to solve that?

Answer 3

$$T(n)-4T(n-1)+3T(n-2)=1~~~(1)$$ After @J. W.Tanner 's suggetion Put $T(n)=x*n$ in $$T(n)+5T(n-1)-7(n-1)+3T(n-2)=0~~()$$ We get $x=3,1,1$, So $$T(n)=C_1 (3)^n+(C_2 n + C_3)1^n~~~(3)$$ By putting (3) in (1), C_2=-1$b %C_1$ and $C_3$ are undetermined. So h fnl luos $$T(n)=C_1 3^n+C_3-n/2.$$