How do I prove that the square root of 2 is irrational using the principle of mathematical induction?
Prove that square root of 2 is irrational using the principle of Mathematical Induction
4
$\begingroup$
induction
rationality-testing
-
0http://math.stackexchange.com/questions/917983/the-proof-of-sqrt2-is-not-rational-number-via-fundamental-theorem-of-arithm – 2015-11-20
2 Answers
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: