## Task 6 - 331236

Determine for each natural number $n$ the greatest power of two that is a divisor of the number $\left[(4+\sqrt{18})^{n}\right]$.

Hint: If $r$ is a real number, the integer $g$ such that $g \leq r < g+1$ is denoted by $g=[r]$.
We first note that the following expression

$$
A_{n}:=(4+\sqrt{18})^{n}+(4-\sqrt{18})^{n}=\sum_{k=0}^{\left[\frac{n}{2}\right]}\binom{n}{2 k} 2^{2 n-3 k+1} 3^{2 k} \quad(n \in \mathbb{N})
$$

is always an integer, and more precisely, it is the integer $g$ that results from rounding $(4+\sqrt{18})^{n}$, where for even $n$ it is always rounded up, and for odd $n$ it is always rounded down. With the abbreviation

$$
B_{n}:=\left[(4+\sqrt{18})^{n}\right] \quad(n \in \mathbb{N})
$$

the following relationship thus holds:

$$
B_{n}:= \begin{cases}A_{n}-1, & \text { if } n \text { is even } \\ A_{n}, & \text { if } n \text { is odd }\end{cases}
$$

Since the $A_{n}$ are always even for even $n$ due to their construction, the $B_{n}$ are then automatically odd, meaning the highest power of two that divides $B_{n}$ for an even $n$ is only 1.

If we now assume $n$ to be odd in the following, the observation is of particular importance that in formula (*) we only need to consider the last term for $k=\left[\frac{n}{2}\right]=\frac{n-1}{2}$, as the other terms are clearly divisible by a higher power of two. The highest power of two by which this last term is divisible, however, is

$$
2^{\frac{n+5}{2}}
$$

as can be seen immediately by substituting $k=\frac{n-1}{2}$, which thus also answers the above question for odd $n$.