The sequence $ \{a_n \} $ is defined as follows: $ a_0 = 1 $ and $ {a_n} = \sum \limits_ {k = 1} ^ {[\sqrt n]} {{a_ {n - {k ^ 2 }}}} $ for $ n \ge 1. $ Prove that among $ a_1, a_2, \ldots, a_ {10 ^ 6} $ there are at least $500$ even numbers. (Here, $ [x] $ is the largest integer not exceeding $ x $.)
Problem
Source: SRMC 2019 P4
Tags: combinatorics, Sum, floor function, Even, algebra, function
Pathological
05.08.2019 05:57
Somewhat easy for an SRMC P4.
Let us suppose for the sake of contradiction that there were less than $500$ even numbers among $a_1, a_2, \cdots, a_{10^6}$, say that they are $a_{i_1}, a_{i_2}, \cdots, a_{i_t}$ for $t \le 499.$ For each $1 \le j \le t$, let $S_j = \{i_j+x^2| 0 \le x \le 999\}.$ Observe that there are at most $1000t$ elements which are in at least one of the $S_j$'s, and so since there are $499500$ positive integers $n \in [1, 10^6]$ such that $\left \lfloor \sqrt{n} \right \rfloor$ is even, there must exist some $n$ with $\left \lfloor n \right \rfloor$ even, $n \notin S_1 \cup S_2 \cup \cdots \cup S_t.$ This means, however, that $a_{n-y^2}$ is odd for $0 \le y \le \left \lfloor \sqrt{n} \right \rfloor$ from the definition of the $S_j$'s, and so therefore we have that an odd number ($a_n$) is the sum of an even number ($\left \lfloor \sqrt{n} \right \rfloor$) of odd numbers ($a_{n-k^2}$ for $1 \le k \le \left \lfloor \sqrt{n} \right \rfloor$). This is clearly absurd.
$\square$
txc
03.01.2020 14:33
Define $a_n=0$ for all $n<0$. It is easy to see that $a_n$ counts the number of sequences of positive integers $(b_1,b_2,...,b_k)$ such that $b_1^2+b_2^2+...+b_k^2=n$. For each $n\geq0$, let $S_n$ denote the set of all such sequences. We define an involution $f_n:S_n \to S_n$ as $f_n(b_1,b_2,...,b_k)=(b_k,b_{k-1},...,b_1)$. Since $f_n$ is an involution, the number of fixed points of $f_n$ has the same parity as $|S_n|$. Consider a fixed point $(b_1,b_2,...,b_k)$ of $f_{2n}$. If $k$ is even, say $k=2l$, then $b_1^2+b_2^2+...+b_l^2=n$. There are $a_n$ such sequences. If $k$ is odd, say $k=2l+1$, then $2(b_1^2+b_2^2+...+b_l^2)+b_{l+1}^2=2n$. Note $b_{l+1}$ must be even, so let $b_{l+1}=2c$. Then $b_1^2+b_2^2+...+b_l^2=n-2c^2$. For each $c>0$, there are $a_{n-2c^2}$ such sequences. Therefore, $$a_{2n}\equiv a_n+\sum_{c=1}^\infty a_{n-2c^2} \text{ }(\text{mod } 2)$$Suppose $n$ is not a perfect square (so each sequence in $S_n$ has at least two terms). Define $g_n:S_n \to S_n$ as $g_n(b_1,b_2,...,b_k)=(b_2,b_1,b_3,b_4,...,b_k)$. We similarly want to count the number of fixed points of $g_n$. A fixed point occurs when $b_1=b_2=c$ for some $c>0$. Then $b_3^2+b_4^2+...+b_k^2=n-2c^2$. There are $a_{n-2c^2}$ such sequences. Therefore, $$a_n\equiv\sum_{c=1}^\infty a_{n-2c^2} \text{ }(\text{mod } 2)$$Putting the two equations together, whenever $n$ is not a perfect square, $$a_{2n}\equiv 2\sum_{c=1}^\infty a_{n-2c^2} \equiv 0 \text{ }(\text{mod } 2)$$This evidently gives more than $500$ even numbers in $a_1,a_2,...,a_{10^6}$. $\Box$ Comment. This solution shows that $a_{2n}$ is even if and only if $n$ is not a perfect square. With significantly more work, the parity of $a_{4n+1}$ can be characterized. I was not able to characterize the values of $a_{4n+3}$ , so I will be really interested in a solution that gives those values too.