Difference between minus one and plus one induction?

Question

I recently started a Combinatorics class, in which my teacher (grad student) has instructed us to Prove by induction that $$1^2+2^2+\ldots+n^2 = \frac{n(n+1)(2n+1)}{6} = \frac{2n^3+3n^2+n}{6}$$ this is trivial in the fact that it has been solved many times before, however my professor has insisted I solve it by using $P(n-1)$ as opposed to $P(n+1)$, which I've done below.

Basis

$$\frac{1(1+1)(2*1+1)}{6} = 1$$

Inductive Step $(n-1)$

$$1^2+2^2+\ldots + (n-1)^2 = \frac{(n-1)(n)(2(n-1)+1)}{6}$$ Which Simplifies to $$\frac{(n-1)(n)(2n-1)}{6} \rightarrow \frac{2n^3-3n^2+n}{6}$$ Add $6\frac{n^2}{6}$ to both sides and we've proven by induction.

My question is do there exists any mathematical proofs for which solving by Induction with $n+1$ and $n-1$ are not interchangeable and should I petition my professor to be able to use them interchangeably. I am aware that solving using $n-1$ and $n+1$ is identical, at least for every scenario I've come across (we're working with positive integers so I'm not expecting any variance from that), however given the overwhelming amount of resources, I can't for the life of me figure out why I am being instructed to use a method opposite what seems to be the norm for any other reason besides my teacher's personal preference.

Answer 1

As Michael Burr noted in the comments, the two conventions are identical; it's just a change of name for the variable. You could equally assume $P(k+12)$ holds and prove $P(k+13)$ from that.

The advantage of using $P(n-1) \implies P(n)$ is that your target formula is already expressed in terms of $n$, so you don't have to rewrite the target in terms of $n+1$ to figure out what you're looking for; the advantage of using $P(n) \implies P(n+1)$ is that the inductive hypothesis is already expressed in terms of $n$.

One other advantage of using $P(n-1) \implies P(n)$ is that it transfers better to "strong induction," where you can assume $P(k)$ for all $k < n$ to prove $P(n)$. Here there is definitely less rewriting going on if you use $P(n)$ as opposed to $P(n+1)$ as your target.

I've seen both used widely. I personally usually prefer $P(n-1) \implies P(n)$.

Answer 2

I would argue that, if anything, there are reasons to prefer $P(n) \Rightarrow P(n+1)$.

Natural numbers can be defined in many ways, but the usual inductive definition is the following:

1. $0$ is a natural number;
2. If $n$ is a natural number, then $s(n)$ is a natural number.

Here $s(n)$ denotes the successor of $n$.

These two rules define a set $\mathbb N$ together with an induction principle (which allows us to prove properties of all elements of $\mathbb N$ and is in fact the usual mathematical induction) and a recursion principle (which allows us to construct new objects from the elements of $\mathbb N$).

Then $\mathbb N$ can be endowed with the usual operations satisfying all the well-known properties. In particular, it is customary to write the successor $s(n)$ of $n$ as the sum $n+1$, although it is the sum between two natural numbers that is actually defined by recursion using the successor.

There are of course many inductive structures other than the set of natural numbers. For example, binary trees are defined by:

1. $v$ is a binary tree (a single vertex, which is also the root);
2. If $t_1$ and $t_2$ are binary trees, then $t_1 \bullet t_2$ is a binary tree (the graph formed by taking $t_1$ and $t_2$, adding a new vertex as a root and joining the roots of $t_1$ and $t_2$ to the new root).

How does the induction principle look like for binary trees? If you want to prove that $P(t)$ holds for any binary tree $t$, you have to prove:

1. (Basis) $P(v)$ holds;
2. (Inductive step) If $P(t_1)$ and $P(t_2)$ hold, then $P(t_1 \bullet t_2)$ holds.

In this case there is no equivalent to the predecessor of a natural number.

Answer 3

I think the only reason s/he did it this way is s/he wanted to have the final simplification end in the form $\frac {2n^3 + 3n^2 + n}6$

Had he done $P(n) \implies P(n+1)$ it would have involve a lot of factoring to get in the form $\frac {2(n+1)^3 + 3(n+1)^2 + (n+1)}6$.

Try it:

$1 + 2 + .... + n^2 = \frac {2n^3 + 3n^2 + n}6$

So $1 + 2 + ...... + n^2 + (n+1)^2 = \frac {2n^3 + 3n^2 + n}6 + n^2 + 2n + 1$

$= \frac {2n^3 + 9n^2 + 13n + 6}6$

... and we have to somehow get that to .... $=\frac {2(n+1)^3 + 3(n+1)^2 + (n+1)}6$

... which isn't impossible ...

$\frac {2n^3 + 9n^2 + 13n + 6}6= \frac {2n^3 + 6n^2 + 6n + 2 + 3n^2 + 7n + 4}6$

$=\frac {2(n+1)^3 + 3n^2 + 6n + 3 + n + 1}6$

$= \frac {2(n+1)^3 + 3(n+1)^2 + (n+1)}6$

... but.... why schlep? That factoring and working backwords isn't the point.

It's easier to follow it and to go to the conclusion if you you work toward simplifying.

=====

I suppose an easier compromise would be to do:

$\frac {2(n+1)^2 + 3(n+1)^2 + (n+ 1)}{6} = \frac {2n^3 + 6n^2 + 6n + 2 + 3n^2 + 6n + 3 + n+1}6 = \frac {2n^3 + 9n^3 + 13n + 6}6$

first.

Then:

$1+2 + ..... + n^2 + (n+1)^2 =$

$\frac {2n^3 + 3n^2 + n}6 + (n+1)^2 = \frac {2n^3 + 3n^2 + n}6 +n^2 + 2n + 1=$

$\frac {2n^3 + 3n^2 + n + 6n^2 + 12n + 6}6 = \frac {2n^3 + 9n^3 + 13n + 6}6$

$= \frac {2(n+1)^2 + 3(n+1)^2 + (n+ 1)}{6}$