How to solve the recurrence relation $T(n)=aT(n-1)+bn^c$ with $T(1)=1$

Question

How to solve this recurrence relation?
$ T(n)=aT(n-1)+bn^c \\T(1)=1,$
where a, b, c are constant.
I want to solve it using generating function, but get stuck. Could anybody help me?

Answer 1

Assuming that $c$ is a positive integer,

Solve the homogeneous recurrence first:

$T(n)=aT(n-1)$, which yields the general solution $T(n)=\alpha a^n$

In the case that $a\neq 1$, next assume that $\beta_0+\beta_1n+\beta_2n^2+\dots+\beta_cn^c = T(n)$ and plug that in place of $T(n)$ and $T(n-1)$.

In the case that $a=1$, instead assume that $\beta_0n+\beta_1n^2+\beta_2n^3+\dots+\beta_cn^{c+1}=T(n)$ and plug that in place of $T(n)$ and $T(n-1)$.

In either case, solve for the coefficients $\beta_0,\dots,\beta_c$.

Once done, you may use initial conditions to solve for $\alpha$

---

Example: $T(n)=2T(n-1)+2n$, $T(1)=1$

Homogeneous solution: $T(n)=\alpha 2^n$

Particular solution: $T(n)=\beta_0 + \beta_1 n$

Plugging in: $\beta_0+\beta_1 n = 2(\beta_0+\beta_1(n-1)) + 2n$

Solving by comparing coefficients of powers of $n$: $\begin{cases} \beta_1 = 2\beta_1 + 2\\ \beta_0 = 2\beta_0 - 2\beta_1\end{cases}$

Implying: $\begin{cases} \beta_1 = -2\\ \beta_0 = -4\end{cases}$

Giving a general solution as: $T(n) = \alpha 2^n - 4 - 2n$

Solving for $\alpha$ using initial conditions: $1 = 2\alpha -4-2$, implying $\alpha = \frac{7}{2}$

Final answer: $T(n) = 7\cdot 2^{n-1}-4-2n$