How do I solve this linear recurrence equation $C(n) = C(n − 1) + 2n − 1$, where $C(1) =0?$

Question

So far I have used substitution to solve this problem but I am stuck at getting the pattern equation:

T(n) = T(n-1) + 2n - 1
=[T((n-1) - 1) + 2(n-1) - 1] + 2n - 1
=T(n-2) + 2n - 3 + 2n - 1
=T(n-2) + 4n - 4
=[T((n-2) - 1) + 2(n-2) - 1] + 4n + 4 
=T(n-3) + 2n - 5 + 4n - 4
= T(n-3) + 6n - 9
*
*
*
T(n) = T(n-k) + k(2n) + ??? //This is the part I am Having issues with.

For me, it is hard to see the last part pattern. I tried to see if I could find some correlation between previous substitutions but I can't seem to piece it together.
This is a link for the resource I used to solve this problem:https://www.youtube.com/watch?v=Ob8SM0fz6p0
I am trying to learn this concept, so step by step is preferred. Otherwise, Thank you for your help.

Answer 1

\begin{align}T(n) &= T(n-1) + 2n - 1\\ T(n-1) &= T(n-2) + 2n - 3\\ T(n-2) &= T(n-3) + 2n - 5\\ &\vdots \\ T(3) &= T(2) + 5\\ T(2) &= T(1) + 3 \end{align}

Sum those equations and you get:

$$T(n) = -1+1+3+5+...+(2n-3)+(2n-1) = n^2-1$$

Answer 2

To clarify the comments for you.

1. Folks are saying "Trye computing $T(0), T(1), T(2), T(3)$ and see if you notice a pattern. In this paritcular problem, the pattern is likely to be obvious.

2. "Telescoping" refers to a sum like $(A-B) + (B - C) + (C - D)$ which, when re-bracketed, looks like $A + (-B + B) + (-C + C) - D = A - D$: the middle parts "fold up" like an old-style mariner's telescope.

For the work you've done, it's often MUCH easier if you don't algebraically simplify too much. In your case, for instance, I'd write \begin{align} T(n) &= T(n-2) + 2n - 3 + 2n - 1 = T(n-2) + 2(2n) - (3 + 1)\\ T(n) &= T(n-3) + 2n - 5 + 2n - 3 + 2n - 1 = T(n-3) + 3(2n) - (5 + 3 + 1)\\ \ldots \\ T(n) &= T(n - n) + n (2n) - ( (2n-1) + (2n - 3) + \ldots + 3 + 1) \\ &= T(0) + n (2n) - ( (2n-1) + (2n - 3) + \ldots + 3 + 1) \\ \end{align} at which point you can plug in $n = 0$, and perhaps a summation formula for the last parenthesized term, and find out an answer.

Answer 3

If

$$C(n) - C(n-1) = 2n-1$$

then

$$C(n-1) - C(n-2) = 2n - 3.$$

If we subtract the last equation from the previous, we get

$$C(n) - 2C(n-1) + C(n-2) = 2.$$

From this equation we get

$$C(n-1) - 2C(n-2) + C(n-3) = 2.$$

Subtracting again gives

$$C(n) - 3C(n-1) + 3C(n-2) - C(n-3) = 0.$$

The characteristic equation of the last recursion is

$$x^3 - 3 x^2 + 3x - 1 = 0,$$

or

$$(x-1)^3 = 0.$$

Therefore, roots of the recursiob are $x_{1,2,3} = 1$.

So, the general solution of the recursion is

$$C(n) = A_1\cdot 1^n + A_2\cdot n\cdot 1^n + A_2\cdot n^2\cdot 1^n,$$

or

$$C(n) = A_1 + A_2\cdot n + A_3\cdot n^2.$$

Now, from the original equation and $C(1) = 0$ we get $C(2) = 3$ and $C(3) = 8$.

From the system

\begin{eqnarray} A_1 + A_2 + A_3 &=& 0 \\ A_1 + 2A_2 + 4A_3 &=& 3 \\ A_1 + 3A_2 + 9A_3 &=& 8 \end{eqnarray}

we find that $A_1 = -1$, $A_2 = 0$ and $A_3 = 1$ and particular solution is

$$C(n) = n^2 - 1.$$