Prove by Induction that every term of the following sequence is irrational

Assume that for some $n$, $x_n$ is rational. We know that $x_n=(3x_{n-1}+1)^{1/2}$. By algebra we have that $\frac{1}{3}(x^2_n-1)=x_{n-1}$ and so we have that $x_{n-1}$ is also rational.

By iterating this argument $n-1$ times we find out that $x_1$ is rational. However, you’ve already noted this isn’t true. Thus $x_n$ couldn’t have been rational. Since this applies for any $n$, there is no value of the sequence that is rational.

To specifically phrase this as being induction, the base case is just noting that $44$ isn’t a perfect square. Now we need to prove the inductive hypothesis

If $x_n$ is irrational then $x_{n+1}$ is irrational.

This statement is logically equivalent to its contrapositive

If $x_{n+1}$ is rational then $x_n$ is rational.

This contrapositive version is proven by my first paragraph, so since the contrapositive is true the original statement is true. Therefore by induction the entire sequence is irrational.


This is an easy proof by induction: if $x_{n+1} $ is rational, it follows that $ x_n $ is rational. This can be read as the implication "$x_n $ irrational $\implies $ $x_{n+1} $ irrational".