Solving Recurrence Equation

[EnterTheArena]

I have a recurrence equation of the form T(n) = aT(n - 1) + bn where T(1) = 1. In trying to solve this equation, I have tried a top-down and bottom-up approach of "unrolling the equation" but found that I am still having trouble and am unable to solve.

When going from the bottom up, I get the following:

T(n)

T(1) = 1
T(2) = a + b2
T(3) = a^2 + ab2 + b3
T(4) = a^3 + a^2b2 + ab3 + b4

I'm not sure if I'm simplifying correctly as I sort of see a pattern but don't see how I'd write it in a general format. Any advice would be great. Thank you

 

[pka]

I have a recurrence equation of the form T(n) = aT(n - 1) + bn where T(1) = 1. In trying to solve this equation, I have tried a top-down and bottom-up approach of "unrolling the equation" but found that I am still having trouble and am unable to solve.
T(n)
T(1) = 1
T(2) = a + b2
T(3) = a^2 + ab2 + b3
T(4) = a^3 + a^2b2 + ab3 + b4

It would be better to write \(\displaystyle T(4)=a^3+2a^2b+3ab+4b~.\)

Are you to solve recurrence? Or write it as a summation?
Are you sure that you have given \(\displaystyle T(1)\) correctly?

 

[EnterTheArena]

Thanks for the reply. I am trying to solve it and T(1) = 1 is what the problem says.

I've continued to work on it an ended up with a summation that looks like this:
\(\displaystyle a^{n-1}+\sum_{k=2}^n a^{n-k}bk\)

Not sure if this is entirely correct or how to solve from this summation.

Also, once I have my solution, I am tasked with using induction to prove it is correct. I've used induction quite a bit so I shouldn't have trouble with that part.

 

[SlipEternal]

Your formula should be the solution. That should be \(\displaystyle T(n)\) for \(\displaystyle n>1\). Now, you can use induction to show your formula satisfies the recurrence relation.