I always puzzled why the two steps are so different in complexity: almost for any proof checking the basis assertion is simple mechanical procedure, while most of the work deferred to proving inductive step. What if we divorce the basis and inductive step? The assertions where basis is true while the inductive step fails are plentiful and easy to come by (e.g. "All natural numbers are odd").

The case where inductive step is valid but basis fails seems to be more subtle. Assertion involving total order on natural numbers are one example ("All natural numbers are greater than 5"). I'm looking for little more sophisticated assertion where we can't bluntly leverage transitivity of the order relation. Any equality where inductive step is valid but basis fails?

The standard lattice technique of converting inequality to equality ( $x \preceq y \Leftrightarrow GCD(x,y)=x $ is one example which hints that equalities where inductive step is valid but basis fails must be common, but I would like to see analytic closed form expression, e.g polynomial.

Edit: Little reflection upon Tomasz comment prompts that the question must be constrained to satisfiable formulas. Then, there exists $N$ such that the assertion is true, and induction step proves that the statement is valid for all numbers greater than $N$. It becomes evident that no polynomial equality fits this requirement.

  • 4
    $\begingroup$ $n=(n+1){}{}{}$? Really, anything which is never true will have the property vacuously. $\endgroup$ – tomasz Dec 18 '12 at 18:28
  • 1
    $\begingroup$ It's not basis or inductive step that fail but the mathematician. It is unclear to me what you want. You can take any true statement as the inductive step and apply it to the wrong problem to get a failing basis. $\endgroup$ – Karolis Juodelė Dec 18 '12 at 18:30
  • $\begingroup$ Tomasz, unsatisfiable predicate is an example which fails both steps, indeed. Let's scope the question to satisfiable formulas. $\endgroup$ – Tegiri Nenashi Dec 18 '12 at 18:41
  • $\begingroup$ It's not clear to me exactly in what way you'd like the base case to fail... $\endgroup$ – Billy Dec 18 '12 at 18:44
  • 1
    $\begingroup$ Because $\mathbb N^{k+1}=\mathbb N^k\times\mathbb N$, simply use the "base" case for the product of two countable sets and we are done. $\endgroup$ – Asaf Karagila Dec 18 '12 at 19:38

Here is an infinite class of such example:

Take your favorite induction equality.

Pick any real number $x \neq 0$.

Add it to one side only.

Then, you get a new equality for which the inductive step still holds [because RHS P(n+1)-RHS P(n),and RHS P(n+1)-RHS P(n)) do not change], but for which $P(1)$ fail.


$$1+2+...+n=\frac{n(n+1)}{2} + \sqrt{2}$$ $$1+2+...+n=\frac{n(n+1)}{2} + 5$$ $$1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6} + 2013e^{\pi\sqrt{2}}$$

As for the modified question.

Any inequality which holds for $n$ large enough should be the case. For example let $P(x)$ be a polynomial. Then

$$2^n >P(n)$$

falls into your category infinitely often.

For equalities, your question is equivalent to the following: Can we find a function $f(n)$ so that $f(1) \neq 0$ and $f(n)=0 \forall n>n_0$. The answer is yes, we can find infinitely many such functions, and it is trivial to do so....

Note that given such a function $f$ you can do the trick I described at the beginning of my answer to produce a problem like you want..

Conversely, given any induction as you want, define $f(n)= RHS(P(n))-LHS(P(n))$, to get a function like I described... Hence the two problems are equivalent....

P.P.S. If you want the inductive step $P(n) \Rightarrow P(n+1)$ to hold for all $n$, not just for $n > n_0$ the problem is a little more subtle. For once, If $P(n)$ is false, then technically $P(n) \Rightarrow P(n+1)$ holds, so the induction step needs only be true for $n > n_0$.

But, the key is that in oder for this to happen, the step $P(n) \Rightarrow P(n+1)$ needs not be reversible. Thus, any induction using a non one to one function helps.

So here it is:

Pick $f$ any non one to one function. Pick $a \neq b$ such that $f^{n_0}(a)=f^{n_0}(b)$ (where by power I mean composition).

Then the claim $f^n(a)=f^n(b)$ is exactly what you want... The inductive step is

$$f^n(a)=f^n(b) \Rightarrow f(f^n(a))=f(f^n(b)) \,,$$

which is trivial.

One simple such example

Let $a_1=-1$ and $a_n=(a_{n-1})^2$. Then $a_n=1$....

  • $\begingroup$ All those formulas are not satisfable $\endgroup$ – Tegiri Nenashi Dec 18 '12 at 19:23
  • 1
    $\begingroup$ @TegiriNenashi I added something more to address your edit. $\endgroup$ – N. S. Dec 18 '12 at 19:27
  • $\begingroup$ @TegiriNenashi Happy now? ;) $\endgroup$ – N. S. Dec 18 '12 at 19:39

Sorry, I just realized that you asked for equalities. Let me know if you'd like me to delete this.

Every natural number is irrational / transcendental / complex.

Every natural number is divisible by $p$: If all natural numbers less than $n\gt p$ are divisible by $p$, then $n-p$ is divisible by $p$, hence $n$ is divisible by $p$.

Every natural number is prime: If all natural numbers less than $n\gt4$ are prime and $n=pq$ with $p,q\gt1$, then $(p-1)q$ and $p(q-1)$ are prime, so $p=q=2$ and $n=4$.


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.