Proving that a closed form is true for $n=k+1$ with induction

Question

I need to prove that a closed form formula is true for n=k+1. I need to use mathematical induction and explain every step, but I'm getting lost on this one. I already found the closed form, and I made a table comparing recursive and closed form outputs, so I know it's correct.

The recurrence is $T(n)=T(n-1)+n^2$ with $T(1)=1$.

The closed form is $T(n)=(1/6)*n(n+1)(2n+1)$

I would assume it should be started off with something like this:

(1). $T(k+1)=T((k+1)-1)+(k+1)^2$ -This is from the definition of the recurrence with $n=k+1$

(2). $T(k+1)=T(k)+(k+1)^2$ -Note that $(k+1)-1=k$

Now I start to get confused. Is this where I can bring in induction and replace $T(k)$ with my closed form that I already have?

Answer 1

$(1)-$ For $n=1$ it is apparent.

$(2)-$ Suppose that the assumption holds for $n=k$, and it means: $T(k)=\frac{k(k+1)(2k+1)}{6}$

$(3)-$ We wanna prove the assumption for $n=k+1$

$T(k+1)=T(k)+(k+1)^2=\frac{k(k+1)(2k+1)}{6}+(k+1)^2=\frac{k(k+1)(2k+1)+6(k+1)^2}{6}=\frac{k(k+1)(2k+1)+6(k+1)(k+1)}{6}=\frac{(k+1)(2k^2+k)+(k+1)(6k+6)}{6}=\frac{(k+1)(2k^2+7k+6)}{6}=\frac{(k+1)(2k^2+4k+3k+6)}{6}=\frac{(k+1)(2k(k+2)+3(k+2))}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$

So the assumption is true

Answer 2

Yes, you can.

Assume that it holds for $n=k$, i.e. $$T(k)=\frac{k(k+1)(2k+1)}{6}.$$ Then, we have $$\begin{align}T(k+1)&=T(k)+(k+1)^2\\&=\frac{k(k+1)(2k+1)}{6}+(k+1)^2\\&=\frac{k+1}{6}\left(k(2k+1)+6(k+1)\right)\\&=\frac{(k+1)(2k^2+7k+6)}{6}\\&=\frac{(k+1)(k+2)(2k+3)}{6}\\&=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}.\end{align}$$ Hence, it holds for $n=k+1$.