Proving solution to recurrence equation using induction

[ATroelstein]

Hello, I have the following recurrence equation

$$T(n)=aT(n-1)+bn$$

Using substitution, I have solved it to the following form

$$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$

Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this proof would be appreciated. Thank you.

 

[CaptainBlack]

Hello, I have the following recurrence equation

$$T(n)=aT(n-1)+bn$$

Using substitution, I have solved it to the following form

$$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$

Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this proof would be appreciated. Thank you.

First, where did you specify that \(T_1=1\) ?

To prove that \[T_n=a^{n-1}T_1+b\sum_{i=2}^n i \;a^{n-i}\ \ \ ...(1)\] Start by showing that the recurrence holds for \(T_2\). Now plug the general term in \((1)\) above and show that it can be written: \[T_{n+1}=a^{(n+1)-1}T_1+b\sum_{i=2}^{n+1} i \;a^{(n+1)-i}\ \ \ ...(2)\]Then that the base case holds and \((1) \Rightarrow (2)\) together prove by induction that \((1)\) is the solution to your recurrence.

You might find this easier to do if you replace the summation by its sum, but it can be done without this.

CB

 

[ATroelstein]

Thanks for the explanation. I have a much better understanding of how to conduct the proof now. I have an additional question now though. In order to turn the summation into the sum, what technique should I be using?

 

[CaptainBlack]

Thanks for the explanation. I have a much better understanding of how to conduct the proof now. I have an additional question now though. In order to turn the summation into the sum, what technique should I be using?

There are a number of approaches, the one I find easiest to remember is:
\[\sum_{k=2}^n k\; a^{n-k}=a^{n-1}\sum_{k=2}^n k\;a^{-k+1}\]

Now we focus on the final summation and put \(x=1/a\), which gives:
\[\sum_{k=2}^n k\;a^{-k+1}=\sum_{k=2}^n k\;x^{k-1}=\left(\sum_{k=1}^n k\;x^{k-1}\right)-x\]
but:
\[\sum_{k=1}^n k\;x^{k-1}=\frac{d}{dx}\sum_{k=0}^n x^k=\frac{d}{dx}\left(\frac{1-x^{n+1}}{1-x}\right)\]

CB

 

[checkitagain]

Hello, I have the following recurrence equation

$$T(n)=aT(n-1)+bn$$

Using substitution, I have solved it to the following form

$$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$

Now I am trying to prove my solution is correct using > > induction, < <
but I'm a bit lost. Any advice on how to conduct this proof
would be appreciated. Thank you.

but:
\[\sum_{k=1}^n k\;x^{k-1}=\frac{d}{dx}\sum_{k=0}^n x^k=\frac{d}{dx}\left(\frac{1-x^{n+1}}{1-x}\right)\]

I wouldn't think that any calculus would be used in this intended induction
problem, as induction and summations have been taught in college algebra
and/or pre-calculus courses, but not taking derivatives.

 

[CaptainBlack]

I wouldn't think that any calculus would be used in this intended induction
problem, as induction and summations have been taught in college algebra
and/or pre-calculus courses, but not taking derivatives.

I did say it was the method that I found esiest to remember not that it was the only method. A non-calculus method follows (probably with errors):

\[\begin{aligned}S_n(x)= \sum_{k=1}^n k\;x^{k-1}&=\left(1+x+x^2+...+n^{n-1} \right)+\left( x+2x^2+...+(n-1)x^{n-1}\right) \\ &=\frac{1-x^n}{1-x}+x \left(1+2x+...+(n-1)x^{n-2} \right)\\ &= \frac{1-x^n}{1-x}+x \left( \sum_{k=1}^n k\;x^{k-1} - nx^{n-1} \right)\\&= \frac{1-x^n}{1-x}+x \left( S_n(x) - nx^{n-1} \right)\end{aligned} \]

Then its just algebra.

CB

 

[chisigma]

Hello, I have the following recurrence equation

$$T(n)=aT(n-1)+bn$$

Using substitution, I have solved it to the following form

$$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$

Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this proof would be appreciated. Thank you.

Let's write the difference equation as...

$\displaystyle T_{n+1}=a\ T_{n} + b\ (n+1)$ (1)

As explained in http://www.mathhelpboards.com/threads/426-Difference-equation-tutorial-draft-of-part-I the solution is given by...

$\displaystyle T_{n}= a^{n}\ (\frac{T_{0}}{a} + \frac{2\ b}{a^{2}} + \frac {3\ b}{a^{3}} + ... + \frac{n\ b}{a^{n}})= T_{0}\ a^{n-1} + b\ \sum_{k=2}^{n} k\ a^{n-k}$ (2)

Kind regards

$\chi$ $\sigma$