Equality such that induction step is valid but basis is not?

Question

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.

Answer 1

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.

Examples:

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

Answer 2

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