Prove that $(n+\sqrt{n^2 -1})^k$ will always be of the form$ (t+\sqrt{t^2 -1})$ where $n$, $k$, $t$ are natural numbers Show that $(n+\sqrt{n^2 -1})^k$ will always be of the form$ (t+\sqrt{t^2 -1})$ where $n$, $k$, $t$ are natural numbers
 A: Let $\sqrt {n^2-1}=\alpha$
Then $(n+\alpha)(n-\alpha)=1$ and it is easy to see (prove by induction) that $(n+\alpha)^k = t+u\alpha \text{ and } (n-\alpha)^k = t-u\alpha$ with $t$ and $u$ integers so: $$1=(n+\alpha)^k(n-\alpha)^k = (t+u\alpha)(t-u\alpha)= t^2-u^2\alpha^2 $$
So $$u\alpha = \sqrt{t^2-1} \text{ and } (n+\alpha)^k=t+\sqrt{t^2-1}$$
A: I enjoyed working this out-cool question man. Here's a straightforward inductive proof:
I'm writing $c$ instead of $n$.
Inductively assume $(c + \sqrt{c^2 - 1})^k = a + b \sqrt{c^2 - 1}$, where $b^2(c^2 - 1) = a^2 - 1$ (the base case is clear). That is, not only can you write it as $t + \sqrt{t^2 - 1}$, but also $t^2 - 1$ is a square times $c^2 - 1$ (I guessed this by working out the first $k$'s for $c =2,3$).
Now to see $k \Rightarrow k+1$, we have $$(c + \sqrt{c^2 - 1})^{k+1} = (a + b \sqrt{c^2 - 1})(c + \sqrt{c^2 - 1}) $$$$= (ac + b(c^2 - 1)) + (a + cb)\sqrt{c^2 - 1}$$It suffices to check that $$(ac + b(c^2 - 1))^2 - 1 = (a + cb)^2(c^2 - 1)$$Expanding both sides gives $$c^2 a^2 + 2c(c^2 - 1)ab + (c^2 - 1)^2 b^2 - 1 = (c^2 - 1)a^2 + 2c(c^2 - 1)ab + c^2(c^2 - 1)b^2$$Cancelling the $ab$ terms, pulling the $a^2$ term to the LHS, and the $b^2$ terms to the RHS, we get $$a^2 - 1=b^2(c^2 - 1) $$our inductive hypothesis. 
A: First of all, notice that if $n$ is an integer and $a = n + \sqrt{n^2-1}$, then $n = \frac{1}{2}(a+\frac{1}{a})$. Next notice that the direction of implication can be reversed here, i.e. if $\frac{1}{2}(a+\frac{1}{a})$ is an integer then a can be written in the form $n + \sqrt{n^2-1}$ where $n$ is an integer by setting $n = \frac{1}{2}(a+\frac{1}{a})$.
With this in mind, we simply have to prove that if $\frac{1}{2}(a+\frac{1}{a})$ is an integer then so is $\frac{1}{2}(a^k+\frac{1}{a^k})$ for any integer $k$. This can be easily seen by induction on $k$ using the binomial expansion of $(a+\frac{1}{a})^k$ and the symmetry of the binomial coefficients.
EDIT:
To clarify the second part, $$\left(a+\frac{1}{a}\right)^k = \left(a^k+\frac{1}{a^k}\right) + \sum_{i=1}^{\lfloor{k/2}\rfloor}{k \choose i} + (\text{if $k$ even}){k \choose k/2}$$
LHS is $k$th power of even number so even. All but first term in RHS are even (by induction hypothesis and fact that central binomial coefficient is even). So $(a^k+\frac{1}{a^k})$ must also be even.
A: The roots of $x+\frac1x=2n$ are $x_n=n+\sqrt{n^2-1}$ and $1/x_n=n-\sqrt{n^2-1}$.
If we can show that
$$
x_n^k+1/x_n^k=2m_{n,k}\tag{1}
$$
(that is, an even integer), then we get the form we want:
$$
x_n^k=m_{n,k}+\sqrt{m_{n,k}^2-1}\tag{2}
$$
Initial Case: for $k=1$, obviously, $x_n^1+1/x_n^1=2n$.
Inductive Case: suppose that $(1)$ holds for all $j<k$, that is, $x_n^j+1/x_n^j=2m_{n,j}$. Then,
$$
\begin{align}
(2n)^k
&=\left(x_n+1/x_n\right)^k\\
&=x_n^k+1/x_n^k+\sum_{j=1}^{k-1}\binom{k}{j}x_n^{k-2j}\\
&=x_n^k+1/x_n^k+\left\{\begin{array}{}
\binom{k}{k/2}+\sum_{j=1}^{k/2-1}\binom{k}{j}(x_n^{k-2j}+1/x_n^{k-2j})&\mbox{if $k$ is even}\\
\sum_{j=1}^{(k-1)/2}\binom{k}{j}(x_n^{k-2j}+1/x_n^{k-2j})&\mbox{if $k$ is odd}
\end{array}\right.\\
&=x_n^k+1/x_n^k+\left\{\begin{array}{}
\binom{k}{k/2}+2\sum_{j=1}^{k/2-1}\binom{k}{j}m_{n,k-2j}&\mbox{if $k$ is even}\\
2\sum_{j=1}^{(k-1)/2}\binom{k}{j}m_{n,k-2j}&\mbox{if $k$ is odd}
\end{array}\right.\tag{3}
\end{align}
$$
When $k$ is even, $\binom{k}{k/2}$ has as many factors of $2$ as there are $1$-bits in the binary representation of $k$ (that is, at least $1$). Therefore, since $(2n)^k$, $\binom{k}{k/2}$ (if $k$ is even), and $2\sum\binom{k}{j}m_{n,k-2j}$ are all even, $(3)$ says that $x_n^k+1/x_n^k$ is even, which validates $(1)$.

Recursion for $m_{n,k}$:
Start with $m_{n,1}=n$, then
$$
m_{n,k}=2^{k-1}n^k-\left\{\begin{array}{}
\frac12\binom{k}{k/2}+\sum_{j=1}^{k/2-1}\binom{k}{j}m_{n,k-2j}&\mbox{if $k$ is even}\\
\sum_{j=1}^{(k-1)/2}\binom{k}{j}m_{n,k-2j}&\mbox{if $k$ is odd}
\end{array}\right.
$$
A: Hint $\rm\ \alpha = n\! +\! \sqrt{n^2\!-\!1}\:$ has norm $\rm\,N(\alpha) = \alpha\alpha' = n^2\!-(n^2\!-\!1) = 1,\:$ so $\rm\:N(\alpha^n) = N(\alpha)^n = 1.\:$ 
Conversely, quadratic numbers of norm $1$ have this form: $\rm\: 1 = (a\!+\!bw)(a\!-\!bw) = a^2\! -\! b^2 w^2,\:$ so $\rm\: b^2 w^2 = a^2\!-\!1\:\Rightarrow\: bw = \sqrt{a^2\!-\!1}\:\Rightarrow\:a+bw = a+\sqrt{a^2-1},\:$ by $\rm\:w^2 > 0,\,$ and wlog $\rm\,b\ge 0.$  
