Question

Use mathematical induction to show that if \(n\) is a positive integers, the sequence 2 mod \(n\), \({2^2}\)mod \(n\), \({2^{{2^2}}}\)mod \(n\), \({2^{{2^{{2^2}}}}}\)mod \(n\), ….. is eventually constant (that is, all terms after a finite number of terms are all the same).

Short answer

By mathematical induction, the result \(P\left( n \right)\) is true for all positive integers \(n\).

Step-by-step solution

To recall the concepts and principles

Mathematical Induction: -The mathematical induction is defined as follows:

Step 1 (Base step): In this step, to prove that the statement is true for n=1.

Step 2(Inductive step): In this case, if the statement is true for n^th iteration, then to prove it is also true for (n+1)^st iteration.

To prove the result using principle of mathematical induction

Let the \(P\left( n \right)\) be the statement: The sequence 2 mod \(n\),\({2^2}\) mod \(n\), \({2^{{2^2}}}\)mod \(n\), \({2^{{2^{{2^2}}}}}\) mod \(n\)….. is eventually constant.

Then by principle of mathematical induction,

For \(n = 1,\,\,n = 2\):

\({2^{2{ \cdots ^2}}}\)mod 1 = 0.

\({2^{2{ \cdots ^2}}}\)mod 2 = 0.

Thus, the result is true for\(n = 1,\,\,n = 2\).

Hence, \(P\left( 1 \right),\,P\left( 2 \right)\) is true.

Let the result be true for \(n = k\) for \(k \ge 2\).

It means, 2 mod \(i\) ,\({2^2}\) mod\(i\), \({2^{{2^2}}}\)mod\(i\), \({2^{{2^{{2^2}}}}}\) mod \(i\)….. for \(i = 1,\,2,\, \cdots ,\,k\).

Thus, \(P\left( k \right)\) is true.

Let us prove the result for \(n = k + 1\).

Let \({a_r}\) be the r^th term modulo \(r\) in the sequence 2 mod \(\left( {k + 1} \right)\),\({2^2}\) mod\(\left( {k + 1} \right)\), \({2^{{2^2}}}\)mod \(\left( {k + 1} \right)\), \({2^{{2^{{2^2}}}}}\) mod \(\left( {k + 1} \right)\)…….

When \(\left( {k + 1} \right)\) is even then there exists a positive integer \(x\) and an odd positive integer \(y\) such that \(k + 1 = {2^x}y\).

For sufficiently large \(j\), \({a_j} \ge x\).

Thus, \({a_j}\) is multiple of \({2^x}\)\( \Rightarrow {a_j}\) mod \({2^x} = 0\).

Since \(P\left( k \right)\) is true, \({a_1},\,{a_2},......\) is eventually constant modulo \(y\).

Thus, it is written as,

\(\begin{aligned}{l}y|{a_{j + 1}} - {a_j}\\ \Rightarrow {2^x}y|{a_{j + 1}} - {a_j}\end{aligned}\).

Therefore, \({a_j}\) mod \(\left( {k + 1} \right)\)=\({a_j}\)mod \({2^x}y\) =0, for sufficiently large \(j\).

When \(\left( {k + 1} \right)\) is odd, then \({2^{\varphi \left( {k + 1} \right)}}\) mod \(\left( {k + 1} \right)\)=1, by Euler’s Theorem.

Since \(\varphi \left( {k + 1} \right) < k\) and it is a positive integer, \(P\left( {\varphi \left( {k + 1} \right)} \right)\) is true.

Thus, the sequence \({a_1},\,{a_2},......\) is eventually constant modulo \(\varphi \left( {k + 1} \right)\).

When this constant is \(c\) then, \({a_i} = {t_i}\varphi \left( {k + 1} \right) + c\) , for sufficiently large \(j\).

Therefore, it is written as,

\(\begin{aligned}{c}{a_{i + 1}} = {2^{{a_i}}}\\ &= {2^{{t_i}\varphi \left( {k + 1} \right) + c}}\\ &= {2^c}{\left( {{2^{\varphi \left( {k + 1} \right)}}} \right)^{{t_i}}}\\ &= {2^c}{1^{{t_i}}}\\ = {2^c}\left( {\bmod \left( {k + 1} \right)} \right)\end{aligned}\)

Further solve the above expression,

\(\therefore {a_{i + 1}} = {2^c}\left( {\bmod \left( {k + 1} \right)} \right)\)

This implies that the sequence \({a_1},\,{a_2},......\) is eventually constant modulo \(\left( {k + 1} \right)\).

Hence, \(P\left( {k + 1} \right)\) is true.

Hence, by the principle of mathematical induction, the result \(P\left( n \right)\) is true for all positive integers \(n\).