<s>[INST] Prove $(1+\sqrt{2})^k= \sqrt{n}+\sqrt{n-1}$ 
Prove that for every $k \in \mathbb{N}$ there exists $n\in \mathbb{N}$ such that $(1+\sqrt{2})^k= \sqrt{n}+\sqrt{n-1}$

I tried to prove it using induction, but I could not move to the next step after assuming the result hold for some $k=m$.
 [/INST] This follows from $(1-\sqrt{2})^k\,(1+\sqrt{2})^k=(-1)^k$ for every integer $k$.  So, if $a_k$ and $b_k$ are integers such that $(1+\sqrt{2})^k=a_k+b_k\sqrt{2}$, then $a_k-b_k\sqrt{2}=(1-\sqrt{2})^k$, making $$a_k^2-2\,b_k^2=(-1)^k\,.$$
Let now $k$ be a nonnegative integer, so $a_k$ and $b_k$ are both nonnegative.  If $k$ is even, set $n:=a_k^2=2b_k^2+1$.  If $k$ is odd, set $n:=a_k^2+1=2\,b_k^2$.  This gives
$$(1+\sqrt{2})^k=\sqrt{n}+\sqrt{n-1}\,.$$

Similar things happen with other quadratic radicals as well.  For an example, for every positive integer $k$, there exists a positive integer $n$ such that $$(2+\sqrt{3})^k=\sqrt{n}+\sqrt{n-1}\,,$$ and the same goes for $(2+\sqrt{5})^k$.  For another example, for every positive integer $k$, there exists a positive integer $n$ such that $$(5+2\sqrt{6})^k=\sqrt{n}+\sqrt{n-1}\,.$$ For one last example, for every positive integer $k$, there exists a positive integer $n$ such that $$(8+3\sqrt{7})^k=\sqrt{n}+\sqrt{n-1}\,.$$
This question is related to Pell's Equation $x^2-dy^2=\pm1$, where $d\in\mathbb{Z}_{>0}$ is non-square.

It turns out that, for any positive integer $p$ and for any nonnegative integer $k$, $$\left(\sqrt{p+1}+\sqrt{p}\right)^k=\sqrt{p_k+1}+\sqrt{p_k}$$
for some nonnegative integer $p_k$.  Clearly, $p_0=0$ and $p_1=p$. (Obviously, this implies also that $\left(\sqrt{p+1}+\sqrt{p}\right)^{-k}=\sqrt{p_k+1}-\sqrt{p_k}$ for all nonnegative integers $k$.)
The case $k$ is even follows by observing that
$$\left(\sqrt{p+1}+\sqrt{p}\right)^2=\left(2p+1+\sqrt{4p(p+1)}\right)^2\,,$$
and so
$$\left(\sqrt{p+1}+\sqrt{p}\right)^k=\left(2p+1+\sqrt{4p(p+1)}\right)^{\frac{k}{2}}\,.$$
It is not difficult to verify that, for any integer $m$,
$$\left(2p+1+\sqrt{4p(p+1)}\right)^m=a_m+b_m\sqrt{4p(p+1)}$$
for some integers $a_m$ and $b_m$.  This implies
$$\left(2p+1-\sqrt{4p(p+1)}\right)^m=a_m-b_m\sqrt{4p(p+1)}\,.$$
Thus, $a_m^2-4p(p+1)\,b_m^2=1$.  Consequently, we take
$$p_k=4p(p+1)\,b_{\frac{k}{2}}^2
\text{ which gives }p_k+1=a_{\frac{k}{2}}^2\,,$$
when $k$ is even.
Now, we solve the case where $k$ is odd.  We note that
$$(\sqrt{p+1}+\sqrt{p})^k=\left(2p+1+\sqrt{4p(p+1)}\right)^{\frac{k-1}{2}}\,(\sqrt{p+1}+\sqrt{p})\,.$$
Hence,
$$(\sqrt{p+1}+\sqrt{p})^k=\left(a_{\frac{k-1}{2}}+b_{\frac{k-1}{2}}\,\sqrt{4p(p+1)}\right)\,(\sqrt{p+1}+\sqrt{p})\,.$$
Ergo,
we can take 
$$p_k:=\left(a_{\frac{k-1}{2}}+2(p+1)\,b_{\frac{k-1}{2}}\right)^2\,p$$
so that
$$p_k+1=\left(a_{\frac{k-1}{2}}+2p\,b_{\frac{k-1}{2}}\right)^2\,(p+1)\,.$$
</s>