# Proving solution to recurrence equation using induction

#### ATroelstein

##### New member
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

##### Well-known member
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

#### ATroelstein

##### New member
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

##### Well-known member
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

• ATroelstein

#### checkittwice

##### Member
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 said:
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.

Last edited:

#### CaptainBlack

##### Well-known member
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

##### Well-known member
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$