3
$\begingroup$

Suppose one proves that for all $n\in\{1,2,3,\ldots\},$ $a_n=a_1$ by means of showing that for every value of $n$ we have $a_{n+1} = a_n,$ the proof being the same for all values of $n.$

If one puts it that way, it looks like mathematical induction: The induction hypothesis is that $a_n=a_1,$ and one uses that in proving that $a_{n+1}=a_1,$ by using the transitivity of equality.

But now suppose the proposition to be proved is stated as $ a_1 = a_2 = a_3 = \cdots.$ Then when one proves that $a_{n+1}=a_n,$ one is not using the previous case, which says $a_{n-1} = a_n,$ so in that respect it does not look like mathematical induction.

  • Is the question of whether this really is or is not mathematical induction substantial, or is this trivial semantic nitpicking?
  • What known proofs have this form?

This question was inspired by this video on youtube, where the following is proved by means of elementary geometry:

Suppose a circle centered at $(0,0)$ has circumference $2^n.$ Consider the set of $2^{n-1}$ points $$ S = \left\{ \text{radius} \times\Big( \cos\left( \tfrac{2\pi k} n\right), \sin \left( \tfrac{2\pi k} n \right) \Big) : \textbf{odd } k \right\}. $$ Let $$a_n = \sum_{x\,\in\, S} \|x - (1,0)\|^{-2}.$$ Then $$a_1 = a_2 = a_3 = \cdots\left({} = \frac {\pi^2} 4\right).$$

This yields a solution to the celebrated “Basel problem” since $$ \lim_{n\to\infty} a_n = \sum_{\textbf{odd } k\,\in\,\mathbb Z} \frac 1 {k^2}. $$

$\endgroup$
  • $\begingroup$ Should say: I'm not sure I understand the issue regarding induction. The two versions of the proposition are different. The first asserts that $a_i=A$ for all $i$, the other asserts merely that all the $a_i$ are equal. If you want to establish that the common value is $A$ you will need some base case in addition to the argument showing equality, which will (I think) make the two proofs look identical. Or am I missing the point? $\endgroup$ – lulu Jan 13 at 19:57
  • $\begingroup$ @lulu : Alright, let's phrase it like this: There is some number $A$ for which for all $n$ we have $a_n=A. \qquad$ $\endgroup$ – Michael Hardy Jan 13 at 20:08
  • 2
    $\begingroup$ It seems to me that for the second version the induction is implicit in the conclusion since $a_{n}=a_{n+1}$ for each $n$ all the $a_i$ are equal; if one is strict this needs proof, by induction. $\endgroup$ – quid Jan 13 at 20:18
  • 1
    $\begingroup$ It is never clear what you really mean when you try to speak about mathematics. So, one has to cover all the bases. $\endgroup$ – MoonLightSyzygy Jan 13 at 20:59
  • 1
    $\begingroup$ "Then when one proves that an+1=an, one is not using the previous case, which says an−1=an, so in that respect it does not look like mathematical induction. " But that IS exactly what mathematical induction does. If it doesn't look like induction that's because you never looked under the hood. When you say $P(n)\implies P(n+1)$ and wipe your hand and walk away, if instead you asked "but why does that mean it's always true" and peeked under the hood you'd see $P(1)\implies P(2);P(2)\implies P(3)... P(n-1)\implies P(n);P(n)\implies P(n+1); ....$. This is induction. Plain and simple. $\endgroup$ – fleablood Jan 15 at 19:06
5
$\begingroup$

There's a precise sense in which induction is needed: there are models of PA$^-$ (= first-order Peano arithmetic without induction) which have a definable function $f$ such that

  • $f(n)=f(n+1)$ for all $n$, but

  • there is some $m$ such that $f(m)\not=f(0)$.

Basically, let $M$ be any model of PA$^-$ in which induction fails for some formula $\varphi(x)$, and let $f$ be defined by $f(x)=0$ if $\forall y<x(\varphi(y))$ and $f(x)=1$ otherwise.

This shows that the "local" fact that each term is the same as the next isn't enough to conclude the desired "global" fact without some induction principles. Here your "$a_n$" is my "$f(n)$." Note that we're not looking at any specific argument here, but rather making a general observation about what axioms are needed to prove the theorem using any method.


As someone interested in reverse mathematics, I'd say that the question of what exactly constitutes induction is quite interesting. However, when it comes to the question "what known proofs have this form," I'm honestly a bit unclear on what exactly the form of proof you have in mind is; I think the argument given would need to be made more explicit to answer that. In general, I would say that proofs tend harder than theorems when it comes to characterization: we have precise ways to talk about when two theorems/questions are equivalent, but telling when two proofs are similar is in my opinion still something we can't satisfyingly do.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

As you point out, you can prove by a single application of proof by induction that $\forall x\in N: a_x=a_1$.

Then you can use this result to prove, without further use of induction, that $\forall x, y \in N: a_x = a_y$ since $a_x=a_1$ and $a_y=a_1$ implies $a_x=a_y$ by substitution. That's the easy way. You can also do it the hard way with a double application of proof by induction with the base case for the first application itself requiring a full proof by induction.

| cite | improve this answer | |
$\endgroup$

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.