Intereting Posts

Showing that $\sum\limits_{n \text{ odd}}\frac{1}{n\sinh\pi n}=\frac{\ln 2}{8}$
Does localization commute with taking radicals?
slope of a line tangent through a point
The diophantine equation $x^2+y^2=3z^2$
How many function are there?
Discriminant of a binary quadratic form and an order of a quadratic number field
How is $ $ simplified to become $ (x+h-x) $?
sequential convergence and continuity
Uniqueness of a continuous extension of a function into a Hausdorff space
Geometric interpretation of reduction of structure group to $SU(n)$.
Map preserving indefinite scalar product must be linear
How to make sense of fractions?
Combinatorial proof of $\sum_{k=0}^{n} \binom{n+k-1}{k} = \binom{2n}{n}$
Prove this consequence of Cramer's theorem.
Is $\Bbb Q(\sqrt 2, e)$ a simple extension of $\Bbb Q$?

The principle of mathematical induction works basically because of the following:

If we have a predicate $P(n)$, then if we have:

- Conditionals involving disjunctions
- If a function is continuous and one-to-one then it's strictly monotonic
- Equivalence relations and power sets.
- Prove that $\int_0^\pi\frac{\cos x \cos 4x}{(2-\cos x)^2}dx=\frac{\pi}{9} (2160 - 1247\sqrt{3})$
- Show that if $g \circ f$ is injective, then so is $f$.
- Prove that $x=0.1234567891011\cdots$ is irrational

P(0) is true, and

P(n) $\implies$ P(n+1) for all nonnegative integers n,

then:

P(m) is true for all nonnegative integers, m.

However, I was concerned what if $P(n)$ is false or what if the base cases were false, what that would mean about $P(n+1)$.

I think I know the answer to my question but I wanted to check the answer with the community.

Say that we know $P(n_0)$ is false. Thus, the implication $P(n_0) \implies P(n_0+1)$ is true vacuously (from the definition of implies). However, our goal in induction is to establish the truth about some implication $P(n)$ for as many n as we can. However, since $P(n_0)$ is false, then from the truth table of an implication $P(n_0) \implies P(n_0 + 1)$ remains true regardless of the truth value of $P(n_0 + 1)$. Thus, even though the implication is true, we are unable to conclude anything about $P(n_0+1)$ (or any other value of n > n_0) because $P(n_0 + 1)$ might be either true or false. The goal was to establish the truth about $P(n_0+1)$, but since we can’t establish which fact is true it (about $P(n_0+1)$), then we cannot continue reasoning about values of $n \geq n_0 + 1$.

Is this correct? Is this why if we have a false statement we cannot have a proof by induction that proceeds correctly? Related to this question, if we find a case were $P(n_0) = False$ but then $P(n_1) = True$ for $n_1 > n_0$, can we still hope to show $P(n_0)$ for $n > n_0$? What about the other way round, if $P(n_0) = True$ but then $P(n_1) = False$, $n_1 > n_0$? Can we still hope induction to help us deduce anything meaningful?

- Conditionals involving disjunctions
- Proof problem: Show that $n^2-1$ is divisible by $8$, if $n$ is an odd positive integer.
- Proving that there is no integer solution to $3996x-3071y=-482$
- Prove that $f(x)=0$ for all $x\in\mathbb{R}$.
- Prove that the greatest integer function: $\mathbb{R} \rightarrow \mathbb{Z}$ is onto but not $1-1$
- Show that a vector that is orthogonal to every other vector is the zero vector
- Prove that $\displaystyle\int_{x=-1}^{1}P_L(x)P_{L-1}\acute (x)\,\mathrm{d}x=\int_{x=-1}^{1}P_L\acute(x)P_{L+1} (x)\,\mathrm{d}x=0$
- Proof of $\gcd(a,b)=ax+by$

If $P(n_0)$ is false then the **implication** $P(n_0) \implies P(n_0+1)$ is true (vacuously, as you’ve pointed out), however, we cannot deduce the truth or otherwise of $P(n_0+1)$ in this case.

The hardest part in a proof by induction is proving $P(n) \implies P(n+1).$ If you’ve proved this, then all you have to do is find a suitable $n_0$ such that $P(n_0)$ is true. If $P(n_0)$ is false, but $P(n) \implies P(n+1)$, then pick a different value for $n_0$ (assuming that one exists). If you can find just one such $n_0$ (and if you’ve proved that $ \forall n, P(n) \implies P(n+1)$, then $P(n)$ is true for all $n \geqslant n_0$, by the principle of mathematical induction.

In this case, pick a different value of $n_0$ until $P(n_0)$ is true.

Regarding your last sentence, if $P(n_0)$ is true and $P(n) \implies P(n+1)$, then, by the property of implication, $P(n_0+1)$ is true, as is $P(n_0+2), P(n_0+3), …$, so you’d never have $P(n_1)$ being false (for any $n_1 \geqslant n_0$)!

What you’ve said is correct, but it’s not the usual way that we deal with “false cases”.

Consider the statement $P(n)$ that says

$$

3\ln(1 + n) < n.

$$

You might try proving this is true for every $n$, but you’d fail: it’s false for $n = 0$ and $n = 1$. This is fairly common: namely, it’s often the case that for finitely many values of $n$, $P(n)$ is false. Clearly you therefore can’t prove $P(n)$ true for all $n$. You can, however, often find some $n_0$ with the property that all the “bad” $n$s are less than $n_0$. In the example, $n_0 = 6$ works.

So you typically prove instead that the statement is true for all $n > n_0$.

Alas, the principle of induction doesn’t apply directly.

The usual subterfuge is to consider a new $S(n) = P(n + n_0)$. (So $S(0)$ says that $P(n_0)$ is true, and $S(1)$ says that $P(n_0 + 1)$ is true, and so on.)

The principle of induction then applies to the statments $S(n)$, for $n = 0, 1, …$ and from their truth, you can deduce the truth of $P(n)$ for $n = n_0, n_0 + 1, n_0 + 2, \ldots$.

If the base case is false, then you can’t prove anything. The basic idea of induction is that the two steps mean that $P(0)$ is true, and $P(0)\implies P(1)$, so $P(1)$ is true, and $P(1)\implies P(2)$, so $P(2)$ is true, etc. So “induction” encodes our intuition that this is enough to prove it for every natural number.

If you’ve proved $P(0)$ and $\forall n(P(n)\implies P(n+1))$ then you can’t get any natural number $n$ for which $P(n)$ is false. That is the nature of induction.

Essentially, induction can be seen as a computer program which can take a number $n$ and product a finite proof of $P(n)$.

But without the initial step, then entire thing falls apart. For example, “Every natural number is even and odd”, written as:$$P(n):=\exists k(n=2k)\land \exists \ell(n=2\ell+1)$$ is clearly false, but we can prove $P(n)\implies P(n+1)$. Since $P(0)$ is not true, we can’t prove it.

Note that you aren’t really “assuming $P(n)$ is true,” except as part of proving that $\forall n: P(n)\implies P(n+1)$. You are just saying “if $P(n)$ is true, then $P(n+1)$.” The natural of implications is that you want to deduce $P(n+1)$ from the assumption that $P(n)$ is true. So it doesn’t matter *if* $P(n)$ is true here, as my example above shows.

- Intersection of cyclic subgroups: $(x^m) \cap (x^n) = (x^{lcm(m,n)})$
- Conditions for matrix similarity
- Computing the characteristic function of a normal random vector
- Minimal polynomial of $\alpha^2$ given the minimal polynomial of $\alpha$
- Computing 2d radially symmetric Fourier transforms (with Wolfram Alpha)
- Statistical Inference Question
- Is $(\pmb{1} + \pmb{\eta})\cdot\pmb{\omega_1} = \pmb{1} + \pmb{\eta}\cdot\pmb{\omega_1}$?
- If $Var(X)=0$ then is $X$ a constant?
- $f^+\mathscr{G}$ not a sheaf even if $\mathscr{G}$ is
- Show that every ideal of the matrix ring $M_n(R)$ is of the form $M_n(I)$ where $I$ is an ideal of $R$
- Module isomorphisms and coordinates modulo $p^n$
- An identity on Stirling number of the first and the second kind.
- Is there an isomorphism of additive groups between $\mathbb{Q/Z}$ and $\mathbb{Q}$?
- When is $C_0(X)$ separable?
- Asymptotic expression for sum of first n prime numbers?