Expansion of $(1+\sqrt{2})^n$ I was asked to show that $\forall n\in \mathbb N$ there exist a $p\in \mathbb N^\ast$ such that $$(1+\sqrt{2})^n = \sqrt{p} + \sqrt{p-1}$$ 
I used induction but it wasn't fruitful, so I tried to use the binomial expansion of $(1+\sqrt{2})^n$ but it seems I lack some insight to go further. 
Any hint is welcomed.
 A: This is a bit more roundabout than Jyrki's answer, but I have a soft spot for linear recurrences. 
First, prove that $(1+\sqrt{2})^n=a_n+b_n\sqrt{2}$ where
$$a_0=1,\quad a_1=1,\quad a_n=2a_{n-1}+a_{n-2}\\
b_0=0,\quad b_1=1,\quad b_n=2b_{n-1}+b_{n-2}$$
Then prove that
$$a_n=\tfrac{1}{2} (1 + \sqrt{2})^n + \tfrac{1}{2}(1 - \sqrt{2})^n\\
b_n=\tfrac{1}{2\sqrt{2}} (1 + \sqrt{2})^n - \tfrac{1}{2\sqrt{2}}(1 - \sqrt{2})^n$$
Now conclude that $a_n^2=2b_n^2+1$, so that $$(1+\sqrt{2})^n=a_n+b_n\sqrt{2}=\sqrt{a_n^2}+\sqrt{a_n^2-1}$$
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
It's reduced to show that the $\ul{following\ expression}$ is an integer:
\begin{align}
\bracks{\pars{1 + \root{2}}^{n} + \pars{1 + \root{2}}^{-n} \over 2}^{2} =
{1 \over 4}\bracks{\pars{1 + \root{2}}^{2n} + \pars{1 - \root{2}}^{2n}} + \half
\end{align}

\begin{align}
&\color{#f00}{\half +
{1 \over 4}\bracks{\pars{1 + \root{2}}^{2n} + \pars{1 - \root{2}}^{2n}}}
\\[5mm] & =
\half + {1 \over 4}\bracks{\sum_{k = 0}^{2n}{2n \choose k}2^{k/2} + 
\sum_{k = 0}^{2n}{2n \choose k}\pars{-1}^{k}2^{k/2}}
\\[5mm] & =
\half + {1 \over 4}\bracks{2\sum_{k = 0}^{n}{2n \choose 2k}2^{k}} =
\half + \half\bracks{1 + \sum_{k = 1}^{n}{2n \choose 2k}2^{k}} =
\color{#f00}{1 + \sum_{k = 1}^{n}{2n \choose 2k}2^{k - 1}}
\end{align}
$\ul{which\ is\ an\ integer\,\,\,}$.


Indeed, the right hand side is $\ds{\ul{the\ value}\ \mbox{of}\ p}$:
  $$
\color{#f00}{\pars{1 + \root{2}}^{n}} =
\color{#f00}{\root{1 + \sum_{k = 1}^{n}{2n \choose 2k}2^{k - 1}} +
\root{\sum_{k = 1}^{n}{2n \choose 2k}2^{k - 1}}}
$$

A: For any $n\in\mathbb{N}$, $(1+\sqrt{2})^n$ is an algebraic number over $\mathbb{Q}$ with degree $\leq 2$, so, assuming that equality holds, $\sqrt{p}+\sqrt{p-1}$ has to be an algebraic number over $\mathbb{Q}$ with degree $\leq 2$. No issues with $p=1$ and $p=2$, but if $p\geq 3$ and neither $p$ or $p-1$ is a square... let us see. Since
$$ (\sqrt{p}+\sqrt{p-1})^2 = 2p-1+2\sqrt{p(p-1)} $$
the biquadratic polynomial
$$ q(x) = x^4+(2-4p)x^2+1 $$
vanishes at $x=\sqrt{p}+\sqrt{p-1}$. If we prove that $q(x)$ is the minimal polynomial of $\sqrt{p}+\sqrt{p-1}$ over $\mathbb{Q}$ we are done and doomed, since we have that $\sqrt{p}+\sqrt{p-1}$ is an algebraic number of degree $4$ over $\mathbb{Q}$. The roots of $q(x)$ are given by $\pm\sqrt{p}\pm\sqrt{p-1}$, but for every choice of signs $\varepsilon_i$
$$ (x-\varepsilon_1\sqrt{p}-\varepsilon_2\sqrt{p-1})(x-\varepsilon_3\sqrt{p}-\varepsilon_4\sqrt{p-1})\not\in\mathbb{Q}[x]$$
by Vieta's formulas, so $q(x)$ is actually the minimal polynomial of $\sqrt{p}+\sqrt{p-1}$ over $\mathbb{Q}$ and the original problem boils down to checking if equality is achieved by some $n$ just in the cases for which $p$ is a square or a square plus one. However, it is easy to check that by expanding
$$ (1+\sqrt{2})^n = a_n+b_n\sqrt{2} $$
we must have $a_n^2=p$ and $2b_n^2=p-1$ or $a_n^2=p-1$ and $2b_n^2=p$. The ratio $\frac{a_n}{b_n}$ of the Lucas-Pell numbers $a_n,b_n$ converges pretty fast to $\sqrt{2}$, and since $\color{red}{a_n^2-2b_n^2=(-1)^n}$, we have:
$$ (1+\sqrt{2})^{2n} = \sqrt{a_{2n}^2} + \sqrt{a_{2n}^2-1} $$
and
$$ (1+\sqrt{2})^{2n+1} = \sqrt{2b_{2n+1}^2}+\sqrt{2b_{2n+1}^2-1}.$$
A: The binomial formula shows you that
$$(1+\sqrt2)^n=a_n+b_n\sqrt2$$
for some integers $a_n, b_n$.
But, the same binomial formula shows you that (convince yourself of this)
$$
(1-\sqrt2)^n=a_n-b_n\sqrt2
$$
for the same integers $a_n,b_n$.
Then comes the hint: Calculate both $$(a_n+b_n\sqrt2)(a_n-b_n\sqrt2)$$ and
$$(1+\sqrt2)^n(1-\sqrt2)^n=[(1+\sqrt2)(1-\sqrt2)]^n$$ and compare.

 You will get that $a_n^2-2b_n^2=(-1)^n$, so $a_n^2$ and $2b_n^2$ differ from each other by one, and $p$ will be the larger of the two.

A: Note:
I added some lines to 
show this explicit formula:
$p
=1+\sum_{k=0}^{n-1} \binom{2n}{2k}2^{n-k-1}
$.
If
$(1+\sqrt{2})^n = \sqrt{p} + \sqrt{p-1}
$,
then
$(1+\sqrt{2})^{2n} = 2p-1+2\sqrt{p(p-1)}
$
so that
$\begin{array}\\
4p(p-1)
&=((1+\sqrt{2})^{2n} - (2p-1))^2\\
&=(1+\sqrt{2})^{4n}-2(1+\sqrt{2})^{2n} (2p-1)+(2p-1)^2\\
&=(1+\sqrt{2})^{4n}-2(1+\sqrt{2})^{2n} (2p-1)+4p^2-4p+1\\
\text{so that}\\
-1
&=(1+\sqrt{2})^{4n}-2(1+\sqrt{2})^{2n} (2p-1)\\
\implies\\
2p-1
&=\frac{(1+\sqrt{2})^{4n}+1}{2(1+\sqrt{2})^{2n} }\\
&=\frac12(1+\sqrt{2})^{2n}+\frac{1}{2(1+\sqrt{2})^{2n} }\\
&=\frac12(1+\sqrt{2})^{2n}+\frac12(-1+\sqrt{2})^{2n}
\qquad\text{ since} (1+\sqrt{2})(-1+\sqrt{2})=1\\
&=\frac12\sum_{k=0}^{2n} \binom{2n}{k}(\sqrt{2})^{2n-k}(1+(-1)^k)\\
&=\sum_{k=0}^{n} \binom{2n}{2k}(\sqrt{2})^{2n-2k}\\
&=\sum_{k=0}^{n} \binom{2n}{2k}2^{n-k}\\
&=\binom{2n}{2n}2^{n-n}+\sum_{k=0}^{n-1} \binom{2n}{2k}2^{n-k}\\
&=1+\sum_{k=0}^{n-1} \binom{2n}{2k}2^{n-k}\\
&=1+2\sum_{k=0}^{n-1} \binom{2n}{2k}2^{n-k-1}\\
\text{so}\\
p
&=1+\sum_{k=0}^{n-1} \binom{2n}{2k}2^{n-k-1}\\
\end{array}
$
