4
$\begingroup$

How do I prove that the square root of 2 is irrational using the principle of mathematical induction?

  • 0
    http://math.stackexchange.com/questions/917983/the-proof-of-sqrt2-is-not-rational-number-via-fundamental-theorem-of-arithm2015-11-20

2 Answers 2

2

The usual proof starts out something like "suppose for a contradiction $\sqrt 2$ were rational, and write it as $p/q$ in lowest terms ...".

The "in lowest terms" hides an instance of induction, which you can unfold to get a proof in the shape of

Theorem. For all positive integers $p$ and $q$, it holds that $(p/q)^2\ne 2$.

Proof. By long induction on $q$. If $p$ and $q$ have a common factor $n>1$ then $(\frac pq)^2 = (\frac{p/n}{q/n})^2$, and since $q/n, the induction hypothesis guarantees that $(\frac pq)^2\ne 2$. Now we consider the case that $p$ and $q$ are relatively prime ...

  • 0
    @JenniferDylan: Yes, they are synonyms. I learned it as long induction, but there are others who call it strong instead.2012-08-17
-1

This is as simple as I could make it in my mind, working on the simply basis of multiple factors (similar to the above) but less algebraic manipulation:

enter image description here