(OIM 2006, P4)

Determine all pairs $(x, y)$ of natural numbers such that $2^{2 x+1}+2^{x}+1=y^{2}$.

## Solutions
We test small cases.

- $x=0$ gives $2^{2 x+1}+2^{x}+1=2+1+1=4=2^{2}$, so $(0,2)$ is a solution.
- $x=1$ gives $2^{2 x+1}+2^{x}+1=8+2+1=11$, which is not a perfect square, so $x=1$ does not yield any solution.
- $x=2$ gives $2^{2 x+1}+2^{x}+1=32+4+1=37$, which is not a perfect square, so $x=2$ does not yield any solution.

Now suppose that $(x, y)$ is a solution with $x \geq 3$. Since $x \geq 3 > 0$, $y^{2}$ must be odd, and thus $y$ must also be odd: we write $y=2 k+1, k \in \mathbb{N}$. Then the equation can be rewritten as $2^{x}\left(2^{x+1}+1\right) = (2 k+1)^{2}-1 = 2 k(2 k+2) = 4 k(k+1)$, so $k(k+1) = 2^{x-2}\left(2^{x+1}+1\right)$, in particular $k > 0$ (the right-hand side is non-zero). Since $k$ and $k+1$ are consecutive integers, one is even and the other is odd. In particular, $2^{x-2}$ divides $k(k+1)$ but is coprime with one of the two (the odd one), so $2^{x-2}$ divides one or the other (by Gauss's lemma).

- Suppose $2^{x-2}$ divides $k$. There exists an integer $m \geq 1$ such that $k = 2^{x-2} m$, and then $k+1 = 2^{x-2} m + 1$. Substituting back into the equation, $m\left(2^{x-2} m + 1\right) = 2^{x+1} + 1$ so $2^{x-2}\left(m^{2} - 8\right) = 1 - m$. If $m \geq 3, 2^{x-2}\left(m^{2} - 8\right) > 0 > 1 - m$, which is impossible. If $m = 2, -4 \times 2^{x-2} = -1$, which is impossible because 4 does not divide 1. Finally, if $m = 1, -7 \times 2^{x-2} = 0$, which is also impossible. Therefore, this case is impossible.
- Now suppose $2^{x-2}$ divides $k+1$. There exists an integer $m \geq 1$ such that $k+1 = 2^{x-2} m$, and then $k = 2^{x-2} m - 1$. Substituting back into the equation, $m \times \left(2^{x-2} m - 1\right) = 2^{x+1} + 1$ and thus $2^{x-2}\left(m^{2} - 8\right) = 1 + m$. Since $1 + m > 0$, then $m^{2} - 8 > 0$ and thus $m \geq 3$. Then $1 + m = 2^{x-2}\left(m^{2} - 8\right) \geq 2\left(m^{2} - 8\right)$ because $x-2 \geq 1$ and $m^{2} - 8 > 0$. Then $2 m^{2} - m - 17 \leq 0$ so $m(2 m - 1) \leq 17$. The left-hand side is increasing in $m$, and at $m = 4$ we have $4 \times (2 \times 4 - 1) = 28 > 17$ so for $m \geq 4$, the inequality is not satisfied. The only possibility is thus $m = 3$. Substituting, we get $2^{x-2} \times \left(3^{2} - 8\right) = 1 + 3$ so $2^{x-2} = 4$, hence $x - 2 = 2$, and then $x = 4$. We verify: $2^{2 x+1} + 2^{x} + 1 = 512 + 16 + 1 = 529 = 23^{2}$, so $(4, 23)$ is a solution.

In conclusion, there are exactly two solutions, $(x, y) = (0, 2)$ and $(x, y) = (4, 23)$.

## 3 Second Part: Geometry & Combinatorics

## 1 Double Counting 1 (Raphael)

## Exercises on Double Counting

For double counting exercises, the first question to ask is: "What do we need to count?"