Irrationality of $\sqrt 2$ using induction I came upon this exercise in a textbook.
I know that $\frac{n}{b} \ne \sqrt{2} $ for all $b \gt 0$ and $n \le N_0$.
How can I then show that $\frac{N_0 + 1}{b} \ne \sqrt{2}$ for all $b \gt 0$?
 A: Let $$\frac{N_{0}+1}{b}=\sqrt{2}\rightarrow (N_{0}+1)^{2}=2b^{2}$$
Obviously $N_{0}+1>b$ or $N_{0} \geq b$.
We can see that $N_{0}+1$ is divisible by 2. Let $N_{0}+1=2t$ $$4t^2=2b^2\ \rightarrow\ 2t^{2}=b^{2}\ \rightarrow\ \frac{b}{t}=\sqrt{2}$$
Hence we have found a number $b\leq N_{0}$ such that the given condition holds true which is a contradiction!
A: Hint $\ $ Key idea: $\,\color{#0a0}{\rm descent}$ follows by taking the $\,\rm\color{#c00}{FP\, (fractional\  part)}\,$ of equal fractions, e.g. $\,\frac{42}{10} = \frac{63}{15}\,\stackrel{\color{#c00}{\rm FP}}\Rightarrow\, \frac{2}{10 }= \frac{3}{15}\ $ by subtracting from both their integer part $= 4.\,$  Applying this below
$$\sqrt{N}\, = \frac{N}{\sqrt{N}}\, \Rightarrow\, \frac{A}B = \frac{NB}{A}\ \color{#c00}{\stackrel{\rm FP}\Rightarrow}\, \frac{b}B = \frac{a}A\, \Rightarrow\, \frac{A}B = \frac{a}{b}\ \ \ {\rm for}\ \ \ \begin{eqnarray}\color{#0a0}{0<a<A} \\ 0<\,b<B\end{eqnarray}$$
where $\,a,b\ne 0,\,$ else $\,\sqrt{N} = A/B\,$ has zero fractional part, i.e. it is an integer, contra hypothesis.
Hence, by descent: $ $ given any fraction $ = \sqrt{N}\,$ there is one with smaller numerator $\,\color{#0a0}{a < A}.\,$ Or, contrapositively, by complete induction: if no  $\ a < A\,$ is a numerator for $\,\sqrt{N}\,$ then neither is $\,A.$ 
Remark $\ $ The classical proof in Michael Hardy's answer is a special case since, for fractions in the interval $\,[1,2),\,$ taking the fractional part $(\color{#c00}{\rm FP})$  amounts to $\,\color{#c00}{\rm subtracting\ 1},\,$ so, as above,
$$\sqrt{2}\, = \frac{2}{\sqrt{2}}\, \Rightarrow\, \frac{A}B = \frac{2B}{A}\ \color{#c00}{\stackrel{\rm FP}\Rightarrow}\, \frac{A\!-\!B}B = \frac{2B\!-\!A}{A}\, \Rightarrow\, \frac{A}B = \frac{2B\!-\!A}{A\!-\!B}$$
The proof in Shaswata's answer is the classical proof by cancelling  $2,\,$ in fraction form, i.e.
$\quad\displaystyle \sqrt{2}\, = \frac{2}{\sqrt{2}}\,\Rightarrow \frac{\color{#c00}A}B = \frac{2B}{A} = \frac{\color{#c00}B}{\color{#0a0}{A/2}}\,\ $  by $\ \displaystyle\left[\! \begin{eqnarray}  2B^2 = A^2&&\\ \ \Rightarrow\  \color{#0a0}{2\,\mid A}\  &&\end{eqnarray}\!\!\right].\ $  $\,\left[\begin{eqnarray}\\ {\rm So \ \ } \color{#c00}{A>B}\ \ \ {\rm by}&&\\ \sqrt{2}\, = \frac{A}B>1&&\end{eqnarray}\!\!\right]\Rightarrow\,$ descent.
The advantage of the first proof is that if one attempts to extend the prior proof to general square roots then one needs more power, viz. the prime divisor property: prime $\,p\mid ab\,\Rightarrow\, p\mid a\,$ or $\,p\mid b,\,$ or some equaivalent, e.g. uniqueness of prime factorizations. However, the first proof uses only the division algorithm (conceptually it can be viewed as employing the continued fraction algorithm to prove the uniqueness of reduced fractions or, equivalently, Euclid's Lemma). The continued fraction algorithm is a variant of the Euclidean algorithm. The same methods will work in any domain that enjoys an analogous division with remainder algorithm, i.e. so-claeed Euclidean domains, e.g. any ring $\,F[x]\,$ of polynomials with coefficients in a field.
A: Suppose $(N_0+1)/b=\sqrt{2}$.  Then a bit of algebra shows that $\dfrac{2b-(N_0+1)}{N_0+1-b}=\sqrt{2}$, contradicting the induction hypothesis.
