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

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Recurrence
AI Thread Summary
The recurrence relation T(n) = aT(n-1) + bn^c with T(1) = 1 has been explored through iterative substitution, leading to the expression T(n) = (n-1) + b ∑(k=0 to n-2) a^k(n-k)^c. The poster seeks confirmation on the correctness of this derivation and inquiries if the substitution method is the only approach to solve the recurrence. An alternative form of the difference equation is presented as t_{n+1} = a t_n + b(n+1)^c, with a suggested solution t_n = a^n + b ∑(k=1 to n) a^(n-k) k^c. The discussion highlights the need for clarity on the solution methods for such recurrence relations.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Last edited by a moderator:
Physics news on Phys.org
mathmari said:
Hey! :o

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$
 
Back
Top