16. Пусть a — действительное число, причём \(a+\frac1a\) — целое. Доказать, что при любом натуральном n число \(a^n+\frac1{a^n}\) также целое.

Так как в условии есть \(\frac1a\), то \(a\ne0\). Обозначим целое число \(a+\frac1a\) через \(m\) и положим \(T_n=a^n+\frac1{a^n}\).

Начальные значения: \(T_0=2\), \(T_1=m\) — целые числа.

Для любого \(n\ge1\) выполняется тождество \[\left(a+\frac1a\right)\left(a^n+\frac1{a^n}\right)=a^{n+1}+\frac1{a^{n+1}}+a^{n-1}+\frac1{a^{n-1}},\] то есть \(T_{n+1}=mT_n-T_{n-1}\).

По индукции все \(T_n\) целые: если \(T_n\) и \(T_{n-1}\) целые, то \(mT_n-T_{n-1}\) тоже целое. База задана значениями \(T_0,T_1\), значит утверждение верно для всех натуральных \(n\).