Prove or disprove that there exists a number $u\geq 0$ such that $\lfloor u^n\rfloor -n$ is always even for all $n\geq 1$. I've been thinking about the following problem for almost a full day

Prove or disprove that there exists a number $u\geq 0$ such that $\lfloor u^n\rfloor -n$ is always even for all $n\geq 1$. 

This is from MIT's Putnam seminar series of problems. 
I don't think that such a number should exist. However, I just cannot seem to prove it. Would someone like to venture a hint?
 A: New, improved solution. 
Let $u=(3+\sqrt{17})/2$. We claim that for $n\ge1$ we have $\lfloor u^n\rfloor-n$ is even. 
We note that $u$ and $\overline u=(3-\sqrt{17})/2$ are the roots of $x^2-3x-2$. 
Let $r_n=u^n+\overline u^n$. Then $r_0=2$, $r_1=3$, and $r_n=3r_{n-1}+2r_{n-2}\equiv r_{n-1}\bmod2$ for $n\ge2$, so $r_n$ is an odd integer for all $n\ge1$. 
Note $-1<\overline u<0$
Let $s_n=\lfloor u^n\rfloor$. Then for $n$ odd we have $s_n=r_n$, and for $n$ even we have $s_n=r_n-1$. So, $s_n$ is odd for $n$ odd, and even for $n$ even, and we're done. 
More generally, we could use $u=(a+b\sqrt c)/2$ with $a,b$ odd integers, $c\equiv1\bmod8$, $u>1$, $-1<(a-b\sqrt c)/2<0$. 
This was question A-5 on the 1983 Putnam exam. The solution in the Monthly is very different, with less Number Theory, and more Analysis. I will copy out the first paragraph: 
Inductively, we define a sequence of integers $3=a_1,a_2,a_3,\dots$ and associated intervals $I_n=[(a_n)^{1/n},(1+a_n)^{1/n})$ such that $a_n\ge3^n$, $a_n\equiv n\bmod2$, the sequence $\{(a_n)^{1/n}\}$ is nondecreasing, and $I_{n+1}\subseteq I_n$. When this has been done, $\{(a_n)^{1/n}\}$, being nondecreasing and bounded, will have a limit $u$ which is in $I_n$ for all $n$. Then $(a_n)^{1/n}\le u<(1+a_n)^{1/n}$ will imply $a_n\le u^n<1+a_n$ and so $\lfloor u^n\rfloor=a_n\equiv n\bmod2$ for all $n$. 
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
Previous, not terribly helpful answer, retained for historical reasons:
Let $a,b,c$ be integers. Then $(a+b\sqrt c)^n+(a-b\sqrt c)^n$ is always an integer. Call it $r_n$. 
Let $d$ be any integer dividng both $a$ and $bc$. Then $d$ divides $r_n$ for all $n$. 
Now suppose further that $|a-b\sqrt c|<1$. Then $r_n$ is either $\lfloor(a+b\sqrt c)^n\rfloor$ or $\lfloor(a+b\sqrt c)^n\rfloor+1$, depending on whether $(a-b\sqrt c)^n$ is negative or positive. 
This should give you all you need to construct an example. Try it!
