Calculating the value of $\lfloor(1+\sqrt{2})^{2n}\rfloor$ Problem: Calculate the value of  $\lfloor(1+\sqrt{2})^{2n}\rfloor$ where $n$ is an arbitrary non-negative integer and $\lfloor x\rfloor$ indicates the largest integer not greater than $x$.
What I have tried:
Based on the Binomial Theorem:
$$
(1+\sqrt{2})^{2n} + (1-\sqrt{2})^{2n} = 2\sum_{k=0}^n {2n\choose 2k}2^k \Rightarrow  (1+\sqrt{2})^{2k} = 2\sum_{k=0}^n {2n\choose 2k}2^k - (1-\sqrt{2})^{2n}
$$
Also
$$
(1-\sqrt{2})^{2n} \gt 0 \Rightarrow -(1-\sqrt{2})^{2n} \lt 0 \Rightarrow 2\sum_{k=0}^n {2n\choose 2k}2^k -(1-\sqrt{2})^{2n} \lt 2\sum_{k=0}^n {2n\choose 2k}2^k 
$$
$$
\Rightarrow 2\sum_{k=0}^n {2n\choose 2k}2^k  - 1 \le 2\sum_{k=0}^n {2n\choose 2k}2^k -(1-\sqrt{2})^{2n} \lt 2\sum_{k=0}^n {2n\choose 2k}2^k
$$
$$
\Rightarrow 2\sum_{k=0}^n {2n\choose 2k}2^k - 1 \le (1+\sqrt{2})^{2n} \lt 2\sum_{k=0}^n {2n\choose 2k}2^k 
$$
By the definition of floor function:
$$
\Rightarrow \lfloor(1+\sqrt{2})^{2n}\rfloor\ = -1+2\sum_{k=0}^n {2n\choose 2k}2^k
$$
Calculating $\sum_{k=0}^n {2n\choose 2k}2^k$ seems to be too difficult. My question is: Can I change $\sum_{k=0}^n {2n\choose 2k}2^k$ into something simpler to calculate (maybe a closed form)?
 A: You can get recursions, which might be easier to compute.
Define $a_n=1+\left\lfloor (1+\sqrt{2})^{2n}\right\rfloor$, for $n>0$, and get a recursion:
$$a_{n+1} = 6a_n - a_{n-1}; a_1=6; a_2=34$$
So if you need a bunch of values $a_{n}$, recursion will be faster. It still might be faster to use this formula than your original, since it amounts to $n$ additions and $n$ multiplications by $6$ to compute $a_n$ and multiplication by $6$ can be computed very quickly by most good compilers by computing $6x=4x+2x$.
There is an $O(\log n)$ computation, computing the matrix product:
$$\begin{pmatrix}a_{n-1}\\a_n\end{pmatrix}=\begin{pmatrix}0&1\\6&-1\end{pmatrix}^{n-2}\begin{pmatrix}a_1\\a_2\end{pmatrix}$$
You can compute that matrix power in $O(\log n)$ time by using the method of repeated squaring.

Possibly much simpler application of repeated squarting: Compute $(1+\sqrt{2})^{2n}=(3+2\sqrt{2})^n$ as $b_n+c_n\sqrt{2}$ then $a_n=2b_n$. You can again compute $b_n,c_n$ by the repeated squaring technique in $O(\log n)$ time.
[These formula don't quite work when $n=0$ because $(1-\sqrt{2})^{2\cdot 0}=1$ is not less than $1$.]
