On the inner workings of induction?

85 Views Asked by At

I always had some doubts on the inner workings of induction. So I decided to make a little experiment. I am familiar with the proof that the sum of the first $n$ integers is $\cfrac{n(n+1)}{2}$ so I decided to use it to make an experimentation. Using the technique given here I've made the polynomial:

$$f(x)=-\frac{x^5}{120}+\frac{x^4}{8}-\frac{17 x^3}{24}+\frac{19 x^2}{8}-\frac{107 x}{60}+1$$

Which shares some of the first terms of $\cfrac{n(n+1)}{2}$, namely: $\{\underline 1, \underline 3, \underline 6,\underline{10},\underline{15},20,\dots\}$ from $\{1, 3, 6, 10, 15,21\dots\}$, instead of the sixth term be $21$, I altered it to $20$. Now I'm going to pretend that I think that the sum of the first $n$ integers is given by that polynomial and try to prove by induction. Following the same procedure I found here:

$$f(1)=1$$

$$f(k+1)=-\frac{(k+1)^5}{120} +\frac{(k+1)^4}{8} -\frac{17 (k+1)^3}{24} +\frac{19 (k+1)^2}{8} -\frac{107 (k+1)}{60}+1$$

But $$-\frac{(k+1)^5}{120} +\frac{(k+1)^4}{8} -\frac{17 (k+1)^3}{24} +\frac{19 (k+1)^2}{8} -\frac{107 (k+1)}{60}+1\\ \neq -\frac{k^5}{120} +\frac{(k)^4}{8} -\frac{17 (k)^3}{24} +\frac{19 (k)^2}{8} -\frac{107 (k)}{60}+1+(k+1).$$

Now according to the wikipedia article, I guess that the impossibility of writing it as $f(k+1)$ as $f(k)+(k+1)$ Is what makes this proof invalid. But what actually forbids me of writing $f(k+1)=f(k)+(k+1)$? Well, I'm doing induction on $\Bbb{N}$, I have sum and multiplication, then I guess that the axioms of the algebraic structure (semiring?) I'm working with, isn't it?

So, does this proof fails because It's impossible to write $f(k+1)=f(k)+(k+1)$ due to the semiring axioms and the other proof works because it's possible to write $f(k+1)=f(k)+(k+1)$ due to the semiring axioms?

This question is very important for me, In introductory books that have examples of proofs by induction that one is one of the most repeated. But those books usually seems to be omiting steps (in this case, the omitted step is the idea that those expressions can't be equal due to the semiring axioms.

2

There are 2 best solutions below

3
On BEST ANSWER

If you want to have any chance of proving $\forall n:\sum_{i=1}^n i=f(n)$, then of course it must hold that $$f(n+1)=\sum_{i=1}^{n+1}i=\left(\sum_{i=1}^n i\right) +(n+1)=f(n)+(n+1)$$ For if this were not true, then the claim that $\forall n:\sum_{i=1}^n i=f(n)$ is false, and hence cannot be proven (assuming consistency and bla bla bla).

So yes, ultimately your proof will not work because indeed, generally $f(k+1)\not= f(k)+(k+1)$. This has nothing to do with induction though. No matter what proof strategy you use, it's just impossible to proof this claim, because it's false.

I'm not sure why you are thinking about semi-ring axioms. I feel like you're making this way to complicated. You are trying to proof a false claim, and thus no matter what strategy/method you try, nothing will work.


Edit: I think I see what you mean now. Yes ultimately it does come down to the axioms governing artimatric in the polynomial ring $R[k]$. By these axioms we have: $$a=b\Leftrightarrow a-b=0$$ Since it forms a group under addition, and hence has the cancellation property. Then using the definition of $\dot{}$ and $+$ we find $$-\frac{(k+1)^5}{120} +\frac{(k+1)^4}{8} -\frac{17 (k+1)^3}{24} +\frac{19 (k+1)^2}{8} -\frac{107 (k+1)}{60}+1\\-\left( -\frac{k^5}{120} +\frac{(k)^4}{8} -\frac{17 (k)^3}{24} +\frac{19 (k)^2}{8} -\frac{107 (k)}{60}+1+(k+1)\right)\\=-\frac{k^4}{24}+\frac{5k^3}{12}-\frac{35k^2}{24}+\frac{25k}{12}-1$$ And so by the definition of equality we see that $$-\frac{k^4}{24}+\frac{5k^3}{12}-\frac{35k^2}{24}+\frac{25k}{12}-1\not= 0$$ And hence the claim is false.

So I think you are correct that on a certain level the falsehood (and consequently the failure of the proof) is due to the axioms of the arithmetic in $R[k]$.


Edit2: I was confused; you're not working in a polynomial ring here at all. You're just working in the ring $\mathbb{Q}$. As a matter of fact the expression wouldn't even be well defined in a polynomial ring: having $k$, the indeterminate, over the $\sum$ sign makes no sense. Since I don't feel like rewriting the thing I'll just leave it here, I'm sure you can correct it yourself.

2
On

The axiom you are over-looking is not any of the semi-ring axioms (induction does not hold in any arbitrary semi-ring) but this axiom of the natural numbers:

If $S \subseteq \Bbb N$ and:

$a)\ 0 \in S\\b)\ x \in S \implies x+1 \in S$

(some texts write $s(n)$ or $x'$ instead of $x+1$, especially if addition has not yet been defined).

then $S = \Bbb N$.

This is (one of the forms of) the Principle of Mathematical Induction. There is no hope of proving this, it is taken as an intrinsic property we wish natural numbers to have: we can enumerate them (completely) by "counting".

An induction proof works by taking:

$S = \{k \in \Bbb N: P(k)\}$, for some propositional statement $P$ with subject $k$, and then proving $S = \Bbb N$ using PMI.

I urge you to try to prove $n < 6$ by induction, and see what goes wrong (this is not so different than your original approach).