Is there any proposition provable by induction whose evaluation oscillates for small numbers and is true for all large enough numbers?

Question

Actually, I want a proposition $P(n)$ defined over the natural numbers such that:

1. $P(a)$ is true.
2. $P(b)$ is false.
3. $P(c)$ is true.
4. $a<b<c$.
5. $P(n)$ is true for all $n \geq n_0$.
6. We can prove (5) by induction.

In other words, I want a proposition whose evaluation oscillates for small numbers, and then is true for all sufficiently large numbers.

Is there such thing?

Answer 1

$2^n \ge n^2$ is true at $0$, true at $1$, true at $2$, false at $3$, true at $4$, and then true forever. One can prove by induction that it is true for all $n\ge 4$.

Answer 2

"If $P(n)$ is the $n$th prime then $P(n)\geq 2 n.$"... TRUE for $n=1$. FALSE for $n=2,3,4$. TRUE for $n=5$. For $n\geq 5,$ if $P(n)\geq 2 n$ then $P(n+1)\geq P(n)+2\geq 2 n+2=2(n+1).$ So,by induction on $n$ (for $n\geq 5)$, TRUE for all $ n\geq 5.$

Answer 3

Show that, for fixed $k$, $2^n > n^k$ for large enough $n$ and find a value for $n$ as a function of $k$.

In my answer, I showed that if $k > 2$ and $n > k^2+1$ then $2^n > n^k$. For large $k$ and small $n$, $2^n \le n^k$, so this is an infinite class of problems of the type you seek.

Prove that $n^k < 2^n$ for all large enough $n$

Answer 4

$$ P(n)=\begin{cases} \text{FALSE}, & n\equiv 0\pmod 2 \text{ and } n<n_0\\ \text{TRUE}, & n\equiv 1\pmod 2 \text{ and } n<n_0\\ \text{TRUE}, & \text{ Otherwise. } \end{cases} $$

If you don't want it in functional notation, consider this:

Let $Q(n)$ mean "$n$ is in the set $T$", where $T=\{n\in\Bbb N : P(n)\}$.

Answer 5

Fickle predicate that is eventually always true

Let $P(n)$ be "$n$ is either odd or the product of two distinct numbers more than $1$.".

The sequence of truth-values of $P$ on $1,2,3,...$ is:

$1,0,1,0,1,1,1,...$

It can of course be proven by induction that $P(n)$ is true for every integer $n > 4$.

Predicate that alternates for a long time

Just for fun, here is a predicate that alternates for $9$ terms before breaking the pattern on the $10$-th. However, it does not have the required property of being true of sufficiently large positive integers.

Let $Q(n)$ be "The minimum number of unit-length matchsticks needed to form $n$ unit equilateral triangles is either $2$ or $3$ more than a multiple of $4$.".

The sequence of minimum number of matchsticks needed is:

$3,5,7,9,11,12,14,16,18,19,21,23,24,...$

The sequence of truth-values of $P$ on $1,2,3,...$ is:

$1,0,1,0,1,0,1,0,1,1,0,1,0,...$

Answer 6

Here's one with tuneable parameters (and a fairly natural problem, as well):

"For positive coprime $a$ and $b$, every number greater than $ab - a - b$ can represented as a sum of a non-negative multiple of $a$ and a non-negative multiple of $b$".

Half the numbers (i.e.: $(a-1)(b-1)/2$) below the boundary can be represented as such.

For example, every number larger than 41 can be written as a sum of a positive multiple of 7 and a positive multiple of 8, and 21 of the numbers between 0 and 41 inclusive can't be written like that.

See https://en.wikipedia.org/wiki/Coin_problem for more about this.

Answer 7

$(-1)^n + \frac{n}{C} \ge 0$ holds for positive even integer $n$ or integer $n \ge C$. That is, the truth of the inequality oscillates until $n = C$.

Proof:

1. Assume $(-1)^n + \frac{n}{C} \ge 0$, then $(-1)^{(n+2)} + \frac{n+2}{C} = (-1)^n (-1)^2 + \frac{n}{C} + \frac{2}{C} = (-1)^n + \frac{n}{C} + \frac{2}{C} \ge (-1)^n + \frac{n}{C} \ge 0$. So if true for any integer, it is also true for every second higher integer.
2. For $n = 0$ it gives: $(-1)^0 + \frac{0}{C} = 1 \ge 0$ and is true, thus it holds for every even integer.
3. For $C$ uneven: $n = C$ gives: $(-1)^C + \frac{C}{C} = -1 +1 \ge 0$ is true. Now it holds for all integers $n \ge C$
4. For $C$ even: $n = C + 1$ gives: $(-1)^{(C+1)} + \frac{C+1}{C} = -1 +1+\frac{1}{C} \ge 0$ is true. Now it holds for all integers $n \ge C$
5. QED

You can choose $C > 0$ to fit your needs. You can even choose non-integer $C$, this will slightly change the proof by change of $C$ with ceil(C) in step 3 or 4. ($C = e^\pi$, is more "hidden" than 50.)