Solve Recurrence $$T(n)=aT(n-1)+bn^c$$

[mathmari]

Hey!

I want to solve the following recurrence:
$$T(n)=aT(n-1)+bn^c , T(1)=1$$

I have done the following:

$$T(n)=aT(n-1)+bn^c \\ =a \left ( aT(n-2)+b(n-1)^c\right )+bn^c \\ =a^2T(n-2)+ab(n-1)^c+bn^c \\ =a^2 \left (aT(n-3)+b(n-2)^c\right )+ba(n-1)^c+bn^c \\=a^3T(n-3)+ba^2(n-2)^c+ba(n-1)^c+bn^c \\ = \dots \\ =a^iT(n-i)+b\sum_{k=0}^{i-1}a^k(n-k)^c$$

$n-i=1 \Rightarrow i=n-1$

Then we have the following:

$$T(n)=(n-1)+b \sum_{k=0}^{n-2}a^k(n-k)^c$$

Is it correct?? How can I continue?? (Wondering)

Is the substitution method the only way to solve this recurrence?? (Wondering)

 

[chisigma]

Hey!

I want to solve the following recurrence:
$$T(n)=aT(n-1)+bn^c , T(1)=1$$

I have done the following:

$$T(n)=aT(n-1)+bn^c \\ =a \left ( aT(n-2)+b(n-1)^c\right )+bn^c \\ =a^2T(n-2)+ab(n-1)^c+bn^c \\ =a^2 \left (aT(n-3)+b(n-2)^c\right )+ba(n-1)^c+bn^c \\=a^3T(n-3)+ba^2(n-2)^c+ba(n-1)^c+bn^c \\ = \dots \\ =a^iT(n-i)+b\sum_{k=0}^{i-1}a^k(n-k)^c$$

$n-i=1 \Rightarrow i=n-1$

Then we have the following:

$$T(n)=(n-1)+b \sum_{k=0}^{n-2}a^k(n-k)^c$$

Is it correct?? How can I continue?? (Wondering)

Is the substitution method the only way to solve this recurrence?? (Wondering)

Lets write the difference equation in slightly different form...

$\displaystyle t_{n+1} = a\ t_{n} + b\ (n+1)^{c},\ t_{0}=1\ (1)$

The solving procedure is illustrated in...

http://mathhelpboards.com/discrete-mathematics-set-theory-logic-15/difference-equation-tutorial-draft-part-i-426.html

With simple steps You should obtain...

$\displaystyle t_{n} = a^{n} + b\ \sum_{k=1}^{n} a^{n - k}\ k^{c}\ (2)$

Kind regards

$\chi$ $\sigma$