Expansion of $(1+\sqrt{2})^n$

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.

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}$$

$\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}}} $$