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

Solution 1:

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.

Solution 2:

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".