Problem 1328

To prove that $n + \left\lfloor (\sqrt{2} + 1)^n \right\rfloor$ is odd for all positive integers $n$, we will use the sequence $a_n = (1+\sqrt{2})^n + (1-\sqrt{2})^n$.

1. **Define the sequence $a_n$:**
$$a_n = (1+\sqrt{2})^n + (1-\sqrt{2})^n$$
Notice that $(1-\sqrt{2})^n$ is a very small number for large $n$ because $|1-\sqrt{2}| < 1$. Therefore, $a_n$ is very close to $(1+\sqrt{2})^n$.

2. Recurrence relation:
We can derive a recurrence relation for $a_n$:
$$a_n = 2a_{n-1} + a_{n-2}$$
This can be shown by expanding $(1+\sqrt{2})^n$ and $(1-\sqrt{2})^n$ using the binomial theorem and combining terms.

3. Initial conditions:
Calculate the first few terms of $a_n$:
$$a_0 = 2, \quad a_1 = 2, \quad a_2 = 6$$

4. **Parity of $a_n$:**
We need to show that $a_n$ is even for all $n$. We use induction:
- Base cases:
$$a_0 = 2 \quad (\text{even}), \quad a_1 = 2 \quad (\text{even}), \quad a_2 = 6 \quad (\text{even})$$
- Inductive step:
Assume $a_k$ and $a_{k-1}$ are even for some $k \geq 2$. Then,
$$a_{k+1} = 2a_k + a_{k-1}$$
Since $a_k$ and $a_{k-1}$ are even, $2a_k$ and $a_{k-1}$ are also even, and their sum is even. Thus, $a_{k+1}$ is even.

By induction, $a_n$ is even for all $n$.

5. Greatest integer function:
- If $n$ is odd, then $\left\lfloor (1+\sqrt{2})^n \right\rfloor = a_n$.
- If $n$ is even, then $\left\lfloor (1+\sqrt{2})^n \right\rfloor = a_n - 1$.

6. **Sum $n + \left\lfloor (1+\sqrt{2})^n \right\rfloor$:**
- If $n$ is odd:
$$n + \left\lfloor (1+\sqrt{2})^n \right\rfloor = n + a_n$$
Since $n$ is odd and $a_n$ is even, their sum is odd.
- If $n$ is even:
$$n + \left\lfloor (1+\sqrt{2})^n \right\rfloor = n + (a_n - 1)$$
Since $n$ is even and $a_n$ is even, $a_n - 1$ is odd, and their sum is odd.

Therefore, $n + \left\lfloor (\sqrt{2} + 1)^n \right\rfloor$ is odd for all positive integers $n$.

$\blacksquare$