0
$\begingroup$

This question comes directly out of Rosen's Discrete Mathematics and It's Applications pertaining to Strong Induction.

Use strong induction to prove that $\sqrt{2}$ is irrational. [Hint: Let $P(n)$ be the statement that $\sqrt{2}\neq n/b$ for any positive integer $b$.]

Solution: Let $P(n)$ be the statement that there is no positive integer b such that $\sqrt{2}= n/b$. Basis step: $P(1)$ is true because $\sqrt{2} > 1 \geq 1/b$ for all positive integers b. Inductive step: Assume that $P(j)$ is true for all $j\leq k$, where $k$ is an arbitrary positive integer; we prove that $P(k+1)$ is true by contradiction. Assume that $\sqrt{2} = (k+1)/b$ for some positive integer b. Then $2b^2 = (k+1)^2$, so $(k + 1)^2$ is even, and hence, $k+1$ is even. So write $k+1 = 2t$ for some positive integer $t$, whence $2b^2 = 4t^2$ and $b^2 = 2t^2$. By the same reasoning as before, b is even, so $b = 2s$ for some positive integer $s$. Then $\sqrt{2} = (k + 1)/b = (2t)/(2s) = t/s$. But $t \leq k$, so this contradicts the inductive hypothesis, and our proof of the inductive step is complete.

My confusion comes from how we've proven our inductive step by contradiction. Using our hint, we assume $P(n)$ is $\sqrt{2} \neq n/b$. When we start our proof by contradiction component, we assume $P(n)$ is $\sqrt{2} = n/b$ for some $b$ in terms of some arbitrary positive integer $k$: $\sqrt{2} = k/b$. How does showing that $t \leq k$ contradict our inductive hypothesis? Is it because we assume $k/b$ is in reduced terms, where $k$ can not be any smaller and the fact that $t \leq k$ contradicts this?

What am I lacking in my understanding of the proof by contradiction?

Any help would be much appreciated. Please let me know if you would like any clarification or further explanation of my understanding. Thanks so much in advance!

$\endgroup$
1
$\begingroup$

The key to strong induction is that instead of the inductive hypothesis being of the form, "Suppose $P(K)$ is true for some $K$", it's "Suppose $P(k)$ is true for all $k \leq K$". So the inductive step, i.e. assuming that the inductive hypothesis implies that $P(K + 1)$ is true is done by supposing that for every value $k \leq K$, we've determined that $k$ is just not the numerator of $\sqrt{2}$, but magically enough we've found the solution, and it's $K + 1$. So we assume $b \in \mathbb{N}$ is such that $\frac{K + 1}{b} = \sqrt{2}$. Now we square each side, so \begin{align*} \frac{K + 1}{b} & = \sqrt{2} \\ \Rightarrow \frac{(K + 1)^{2}}{b^{2}} & = 2 \\ \Rightarrow (K + 1)^{2} & = 2 b^{2} . \end{align*} This means that $(K + 1)^{2}$ is a factor of $2$, i.e. it's even, so that means $K + 1$ is even, and thus there is some $t$ such that $2t = K + 1$. Moreover, whatever this $t$ is, we'll be sure that $t \leq K$. So the above becomes \begin{align*} (K + 1)^{2} & = 2b^{2} \\ \iff (2t)^{2} & = 2 b^{2} \\ = 4 t^{2} \\ \Rightarrow 2 t^{2} & = b^{2} . \end{align*} Now by the same reasoning we have that $b$ is even, so we can find some $s \in \mathbb{N}$ such that $b = 2s$. Thus the above becomes. \begin{align*} 2t^{2} & = b^{2} \\ & = (2s)^{2} \\ & = 4 s^{2} \\ \Rightarrow t^{2} & = 2 s^{2} \\ \Rightarrow \frac{t^{2}}{s^{2}} & = 2 \\ \Rightarrow \frac{t}{s} & = \sqrt{2} . \end{align*} Here's the big move. We have that $1 \leq t \leq K$, and moreover $t$ is such that there exists $b' = s = \frac{b}{2}$ for which $\frac{t}{b'} = \sqrt{2}$. So in summary, the inductive hypothesis was that we'd checked $P(k)$ for $k = 1, 2, \ldots, K$. Now, we assume for contradiction that our luck is broken, and that we've finally found that $K + 1$ can be the numerator for $\sqrt{2}$. That is to say, \begin{align*} k < K + 1 & \Rightarrow P(k), \\ k = K + 1 & \Rightarrow \neg P(k) . \end{align*} But what we've actually found is that $\neg P(k) \Rightarrow \neg P(\frac{k}{2})$. Of course, $\frac{k}{2} < k$, so if we assume we've finally found the first solution, then it means we must have missed one earlier on, contradicting the strong inductive hypothesis. That's where the contradiction is. The assumption is that we've found the first, when in fact the existence of a solution implies the existence of an earlier solution which we assumed (inductively) didn't exist.

$\endgroup$
  • $\begingroup$ Your explanation at the end made complete sense. I had arrived at this same conclusion when doing the proof. However, I couldn't interpret the results correctly. Your explanation is excellent. Thanks! $\endgroup$ – abmantha Jun 20 '15 at 7:47

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.