1
$\begingroup$

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.

$\endgroup$
5
  • 4
    $\begingroup$ Are you asking about the difference between $P(n-1)\Rightarrow P(n)$ and $P(n)\Rightarrow P(n+1)$ in the inductive step? Those are identical. I am not quite sure what you mean by induction with $n+1$ vs $n-1$. $\endgroup$ Jan 28 '18 at 18:20
  • $\begingroup$ I know that they are the same as far as my example goes, I was just wondering if there was any reason why my teacher has instructed us using $n-1$ for anything other than his own personal preference, given that I couldn't find any resources online for "Solving induction step with n minus one" or similar. Such that is what I'm being taught actually a mirror of a theorem? I'll update my question for clarity. $\endgroup$
    – jfh
    Jan 28 '18 at 18:24
  • $\begingroup$ Perhaps you can put side-by-side your approach and your instructor's approach. Sometimes one direction is preferred over another due to simplicity or clarity. $\endgroup$ Jan 28 '18 at 18:28
  • $\begingroup$ Well, to be fussy neither are either "with n+1" or "with n-1". One is "with n implying n+1" and the other is "with n-1 implying n". Which if you replace $m$ with $n-1$ become "with n implying n+1" and the other "with m implying m+1" which are obviously the same. $\endgroup$
    – fleablood
    Jan 28 '18 at 19:44
  • $\begingroup$ You can do induction with n implying n-1 to prove for example if P(237) is true and P(n) implies P(n-1) for natural number then P(n) is true for all natural numbers less than or equal to 237. That's kind of ... useless. ... Unless you are proving something integers. For example we can prove $b^{n+m} = b^nb^m$ for all integers by induction by "inducing down" if we need to. $\endgroup$
    – fleablood
    Jan 28 '18 at 19:47
1
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Thank you, I know my question sounds like its teetering on the border between naivety and caution, but I think your answer does well to say that noticing the distinction between the terms of the right hand side can help identify which method to use. $\endgroup$
    – jfh
    Jan 28 '18 at 18:38
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}$

$\endgroup$
1
  • $\begingroup$ Whoa! I just read your professors arithmetic. Whoa. That is is clean and pretty with the $(n^3 - bn^2 + n)+2bn^2 = (n^3 + bn^2 +n)$. This use of conjugates just.... I don't know.. it's elegant. And gives a potential geometric insight as to why this works. It doesn't put one method of induction over another but for this particular proof.... it sure is pretty. $\endgroup$
    – fleablood
    Jan 28 '18 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.