# Another induction problem (concrete case)

We have the succession and its formula: $$1^2+4^2+\cdots+ (3k-2)^2 = \dfrac{k(6k^2-3k-1)}{2}$$

Now we need to apply it for $k+1$: $$1^2+4^2+\cdots+ (3n-2)^2 +(3(k+1)-2)^2 = \\ \dfrac{k(6k^2-3k-1)}{2} + (3(k+1)-2)^2$$

I know that the result must be $\frac{1}{2}(k+1)(6(k+1)^2-3(k+1)-1)$ but I wasn't able to find the elegant solution during the test. I can't even see from where to factor out $k+1$.

Care to give a hint?

-
The last term is $(3k+1)^2$. Expand. Bring whole expression to common denominator $2$. Simplify the top. Since you expect a $k+1$ term, divide the cubic on top by $k+1$ (polynomial division). Miraculously it divides exactly. – André Nicolas Nov 28 '12 at 21:18

First combine everything into a single fraction:

\begin{align*} \frac{k(6k^2-3k-1)}{2} + \big(3(k+1)-2\big)^2&=\frac{k(6k^2-3k-1)}2+(3k+1)^2\\ &=\frac{k(6k^2-3k-1)+2(3k+1)^2}2\\ &=\frac{6k^3-3k^2-k+18k^2+12k+2}2\\ &=\frac{6k^3+15k^2+11k+2}2\;.\tag{1} \end{align*}

At this point the easiest thing to do is to multiply out the desired expression,

$$\frac{(k+1)\left(6(k+1)^2-3(k+1)-1\right)}2\;,$$

and verify that it’s equal to $(1)$. If you want to keep working forward from $(1)$, however, you can. We know that $k+1$ should be a factor of the numerator, so we could simply try to divide it out, but we can easily confirm this: by inspection $k=-1$ is a zero of the numerator, so $k-(-1)=k+1$ is a factor. Ordinary polynomial long division or synthetic division quickly yields the factorization

$$6k^3+15k^2+11k+2=(k+1)(6k^2+9k+2)\;.$$

$6(k+1)^2=6k^2+12k+6$, so $6k^2+9k+2=6(k+1)^2-3k-4=6(k+1)^2-3(k+1)-1$, as desired.

-

Hint $\$ Your question amounts to verifying the following polynomial equality

$$\rm (k\!+\!1)\, f(k\!+\!1) - k\, f(k) =\, 2\,(3k\!+\!1)^2\quad for\quad f(k) =\, 6k^2\! - 3k - 1$$

Since LHS and RHS are polynomials of degree $\color{#C00} 2,$ to prove that they are equal it suffices to check that they have equal values at $\,\color{#C00}3\,$ points. That's easy:  LHS = RHS  holds for $\rm\:k = -1,0,1,\:$ viz. $$\begin{eqnarray}&&\rm k=-1:\ \ f(-1) = 8 \\ &&\rm k\ =\ 0:\ \ \ f(1) = 2\\ &&\rm k\ =\ 1:\ \ \ 2\, f(2)\!-\!f(1) = 32 \end{eqnarray}$$

-