0

Let $p,q\in\mathbb N$.

Prove with induction on $q$: $\forall p\in\mathbb N\hspace{1em}\left(\frac{p}{q}\right)^{2}\neq2$.

Things I already proved and might help:

  1. $p^2\neq2$
  2. if $(\frac{p}{q})^2=2$ then $q<p<2q$
  3. if $(\frac{p}{q})^2=2$ then $(\frac{2q-p}{p-q})^2=2$

I tried to solve it like that:

Basis step: for $q=1 \rightarrow(\frac{p}{1})^2=p^2\neq2$ as we already proved.

Inductive Step: Here I'm stuck.

CStudent
  • 67
  • Wait. If $p, q \in \mathbb{N}$, then $p, q \in \mathbb{Z}$. A fraction of 2 integers is a rational by definition, so $\frac{p}{q} \in \mathbb{Q}$. If $(\frac{p}{q})^2=2$, then $\frac{p}{q}=\pm\sqrt{2}$. We know what $\sqrt{2} \notin \mathbb{Q}$ and $-\sqrt{2} \notin \mathbb{Q}$. So for any $p, q \in \mathbb{N}$, $(\frac{p}{q})^2\neq2$. – Tommaso Thea Mar 09 '23 at 16:16
  • You are totally right. But I was asked to prove it using induction. Otherwise I could take this approach – CStudent Mar 09 '23 at 16:20

2 Answers2

1

A really nice question that would precede this one is would be:

Prove by induction that $\displaystyle{\sqrt{2}}$ is irrational.

Now, this may sound absurd, but I shall show you in answering the above question, in how these questions are related.

$$\mathbf{\text{Proof by Induction}}$$ $$\text{Assume} \space \sqrt{2} ≠ \dfrac{p}{q}, \space p, q \in \mathbb{N} \text{ where this holds inductively for $p \le k, \space k \in \mathbb{N}$} \\ \implies \dfrac{k + 1}{q} = \sqrt{2}$$ $$\implies \left(\dfrac{k + 1}{q}\right)^2 = 2 \tag{1} \\ \implies (k + 1)^2 = 2q^2 \\ \implies (k + 1) \mod 2 \equiv 0 \text{ and let } (k + 1) = 2a, \space a \in \mathbb{N} \\ \implies 4a^2 = 2q^2 \to 2a^2 = q^2 \\ \implies q \mod{2} \equiv 0 \text{ and let } q = 2b, \space b \in \mathbb{N} \\ \implies \sqrt{2} = \dfrac{2a}{2b} = \dfrac{a}{b} \\ \quad \\ \mathbf{\text{Here is the contradiction in our induction}}: \\ \sqrt{2} = \dfrac{a}{b}, \space a < k, \text{ however, we assumed} \sqrt{2} ≠ \dfrac{p}{q}, p = 2a \le k$$

It is clearly visible from $(1)$, is where you question was "deferred" to. Without the context in the first $2$ steps, your question may appear distant with the little information given, but nonetheless uses a similar method applied in the above proof.

Dstarred
  • 2,487
0

After many thoughts that's the answer I have:

basis step: for $q=1 \rightarrow (\frac{p}{1})^2=p^2 \neq 2$ as we already proved.

inductive step: assume it's true for every $q \in [n]$ and prove for $q=n+1$.

Suppose by contradiction that $(\frac{p}{q})^2=2$. from (2) we know that $p<2q$. therefore:

$ \begin{array}{c} p<2q\\ \Downarrow\\ p<2\left(n+1\right)\\ \Downarrow\\ p<2n+2\\ \Downarrow\\ p-n-1<2n+2-n-1\\ \Downarrow\\ p-n-1<n+1\\ \Downarrow\\ p-n-1\leq n\\ \Downarrow\\ p-n-1\in[n] \end{array} $

from (3) we know that $\left(\frac{2q-p}{p-q}\right)^{2}=\left(\frac{p}{q}\right)^{2}=2.$ define: $q'=p-n-1\in[n]$.

therefore:

$\left(\frac{2q-p}{p-q}\right)^{2}=\left(\frac{2\left(n+1\right)-p}{p-\left(n+1\right)}\right)^{2}=\left(\frac{2n+2-p}{p-n-1}\right)^{2}=2$.

define: $p'=2n+2-p\in\mathbb N\hspace{1em},q'=p-n-1\in[n].$ We got: $\left(\frac{p'}{q'}\right)=2.$ contradiction! to our inductive assumption that for every $q\in [n]$ there's no p that $\left(\frac{p}{q}\right)=2$.

therefore we proved that $ ∀p\in \mathbb N\hspace{1em} (\frac{p}{q})^2\neq2$ $\hspace{6em}\blacksquare$

CStudent
  • 67