Proof by induction: is it enough to show 0=0? Let $P_n$ be a proposition, so that $$P_n: 3+11+...+(8n-5)=4n^2-n$$
$P_1:3=4\cdot1^2-1$, $P_2:3+11=4\cdot2^2-2$ etc.
When proving $P_n\to P_{n+1}$, is it enough to show in the second induction step that, by subtracting from both sides we have $$4(n+1)^2-(n+1)=4n^2-n+(8(n+1)-5)\leftrightarrow0=0$$ and therefore $P_n\to P_{n+1}$. Or do I must rewrite $4n^2-n+(8(n+1)-5)$ to $4(n+1)^2-(n+1)$?
 A: I would rather
make the use of induction
extremely clear.
First of all,
I would write
$P_n: 3+11+...+(8n-5)=4n^2-n
$
as
$P_n:
\sum_{k=1}^n (8n-5)
=4n^2-n
$.
This makes the start and end terms
of the sum clear
and reduces the chance of error.
Then
I would show the step
from $P_n$
to $P_{n+1}$
like this:
$\begin{array}\\
\sum_{k=1}^{n+1} (8n-5)
&=\sum_{k=1}^{n} (8n-5)+8(n+1)-5
\qquad\text{split off the last term}\\
&=4n^2-n+8(n+1)-5
\qquad\text{use the induction hypothesis}\\
&=4n^2+7n+3
\qquad\text{algebra}\\
&=4(n+1)^2-(n+1)
\qquad\text{more algebra to get the right side of }P_{n+1}\\
\end{array}
$
which is
$P_{n+1}$,
and we are done.
More generally,
suppose we are given
$a$ and $b$,
and we want to find
$u, v, $ and $w$ such that
$P_n:
\sum_{k=1}^n (an+b)
=un^2+vn+w
$
is true.
Arguing exactly as above,
$\begin{array}\\
\sum_{k=1}^{n+1} (an+b)
&=\sum_{k=1}^{n} (an+b)+a(n+1)+b
\qquad\text{split off the last term}\\
&=un^2+vn+w+a(n+1)+b
\qquad\text{use the induction hypothesis}\\
&=un^2+(v+a)n+w+a+b
\qquad\text{algebra}\\
\end{array}
$
$P_{n+1}$ is
$\sum_{k=1}^{n+1} (an+b)
=u(n+1)^2+v(n+1)+w
$,
so we want
$un^2+(v+a)n+w+a+b\\
=u(n+1)^2+v(n+1)+w\\
=un^2+(2u+v)n+u+v+w.
$
Equating coefficients,
$v+a = 2u+v$
and
$w+a+b = u+v+w$.
From the first,
$u = a/2$.
From the second,
$a+b = u+v
=a/2+v$
so
$v = a/2+b$.
For your problem,
$a=8, b=-5$,
so
$u = 4, 
v=8/2-5
=-1
$.
Note that
$w$ does not seem to be
determined.
For this,
we need the initial value;
either $n=0$ or $n=1$
will work.
Using $n=0$,
the sum is empty,
so we want
$0 = w$.
Using $k=1$,
$P_1$ is
$a+b 
= u+v+w$
or
$w
=a+b-u-v
=a+b-a/2-(a/2+b)
= 0
$.
It is comforting that
both cases lead
to the same result.
Therefore
we have shown that
$\sum_{k=1}^n (ak+b)
=(a/2)n^2+(a/2+b)n
$.
This type of argument
enables us to
both discover a result
and prove it.
In some problems,
this technique
allows us to show that
a particular form
of a summation does not exist,
because the assumption
that the form exists
leads to a contradiction.
