0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ $n-1000$ is either not even or not negative. $\endgroup$ Mar 16, 2016 at 1:21
  • $\begingroup$ Is this true for all large enough $n$? $\endgroup$ Mar 16, 2016 at 1:24
  • $\begingroup$ The edited comment is, I don't know if that's the one you're looking at. It was wrong at first. $\endgroup$ Mar 16, 2016 at 1:25
  • $\begingroup$ Oh sorry, I saw the first version of the comment. $\endgroup$ Mar 16, 2016 at 1:25

7 Answers 7

3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Can you find me another one, where this $n=3$ is larger? Something like, $P(n)$ is true for $n=1,2,...,49$, false for $n=50$, and true for all $n > 50$. Not necessarily for $n=50$, but a big number... $\endgroup$ Mar 16, 2016 at 3:04
  • $\begingroup$ @matheuscscp You just said it yourself. $P_k(n) = (1 \le n \le k-1 \text{ or } k+1 \le n) $ $\endgroup$
    – DanielV
    Mar 16, 2016 at 3:07
  • $\begingroup$ I need some proposition where this "failure value" is "hidden", you know? Something you'd be surprised when you find out. This one is too much obvious... $\endgroup$ Mar 16, 2016 at 3:17
  • $\begingroup$ And something we could use algebraic manipulation to prove the induction step. $\endgroup$ Mar 16, 2016 at 3:20
  • $\begingroup$ I will try to think of something that qualifies. The induction step in the above example does require some (mild) algebraic manipulation. $\endgroup$ Mar 16, 2016 at 3:23
2
$\begingroup$

$$ 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)\}$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Can you find me another one, where this $n=3$ is larger? Something like, $P(n)$ is true for $n=1,2,...,49$, false for $n=50$, and true for all $n > 50$. Not necessarily for $n=50$, but a big number... $\endgroup$ Mar 16, 2016 at 3:04
  • $\begingroup$ A journalist once asked Prof.Leo Morse if he could name a property that was true only for numbers less than a million. Answer: Yes. Question: What property? Answer : Being less than a million...... (And BTW $ n\geq 1000000\to n+1\geq 1000000$ for the induction.) $\endgroup$ Mar 16, 2016 at 12:11
  • $\begingroup$ There is a compendium of sequences of natural numbers. I don't recall its acronym or its name. Perhaps someone else can help. You might find some interesting examples in it. $\endgroup$ Mar 16, 2016 at 12:16
  • $\begingroup$ I came across the name of the site of the compendium of sequences It is OEIS.ORG $\endgroup$ Mar 16, 2016 at 15:37
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .