Prove without induction $2^n \mid (b+\sqrt{b^2-4c})^n + (b-\sqrt{b^2-4c})^n $ 
Prove $2^n \mid (b+\sqrt{b^2-4c})^n + (b-\sqrt{b^2-4c})^n $ for all $n\ge 1$ and $b,c$ are integers.


Is it possible to prove this without induction? 
 A: Since the characteristic polynomial of twice the integer matrix
$$\mathbb P = \left(
\begin{array}{cc}
 b & 1 \\
 -c & 0 \\
\end{array}
\right)$$
is $\lambda^2 - 2 b \lambda + 4c$, its roots are
$$b \pm \sqrt{b^2-4c}.$$
The sum of those roots is its trace.  Because $\mathbb P$ has integral coefficients, all coefficients of $\mathbb P^n$ are integral, whence $(2\mathbb P)^n = 2^n \mathbb P^n$ are obviously divisible by $2^n$.  But the trace of $(2 \mathbb P)^n$ is the sum of the $n^\text{th}$ powers of the eigenvalues, QED.

As others have noted, an induction must be lurking here, if only in the relationship $(2\mathbb P)^n = 2^n \mathbb P ^n$.  But this approach helps make the result immediately obvious.
Edit
There is a close relationship between this solution and one based on the two-term recursion mentioned by Jack D'Aurizio.  That recursion can be represented by the right multiplication of 
$$\mathbb Q = \left(
\begin{array}{cc}
 2b & 1 \\
 -4c & 0 \\
\end{array}
\right)$$
on $(a_{n-1}, a_{n-2})$, producing $(a_n, a_{n-1})$. Note that $\mathbb Q$ and $2\mathbb P$ have the same characteristic polynomial.  The principal difference, then, is that $2\mathbb P$ has all even coefficients whereas $\mathbb Q$ does not, making the result for $2\mathbb P$ a little more evident.
A: The sequence given by:
$$ a_n = \left(b+\sqrt{b^2-4c}\right)^n + \left(b-\sqrt{b^2-4c}\right)^n $$
satisfies the recurrence relation:
$$ a_{n+2} = \color{red}{2}b\cdot a_{n+1} - \color{red}{4}c\cdot a_{n}.$$
Since $\nu_2(a_n)\geq n$ holds for $n=0$ and $n=1$, it holds for every $n$ by the previous relation.
Ok, this is still induction :D
A: We want to show$$2^n\vert\left(\left(b+\sqrt{b^2-4c}\right)^n+\left(b-\sqrt{b^2-4c}\right)^n\right).$$
Using $x-y=\frac{x^2-y^2}{x+y}$ indeed we have
$$ 2^n\vert\left(\left(b+\sqrt{b^2-4c}\right)^n+\left(\frac{4c}{b+\sqrt{b^2-4c}}\right)^n\right) \\ 2^n\vert\frac{\left(b+\sqrt{b^2-4c}\right)^{2n}+4^nc^n}{\left(b+\sqrt{b^2-4c}\right)^n} \\ 2^n\vert\frac{\left(2b^2-4c+2b\sqrt{b^2-4c}\right)^n+4^nc^n}{\left(b+\sqrt{b^2-4c}\right)^n}\\2^n\vert\frac{2^n\left(\left(b^2-2c+b\sqrt{b^2-4c}\right)^n+2^nc^n\right)}{\left(b+\sqrt{b^2-4c}\right)^n}.$$
A: Let $x_1$ and $x_2$ be the roots of the quadratic equation $$x^2 - bx + c = 0$$ 
Then $$x_1 = \frac{b + \sqrt{b^2 - 4c}}{2}$$ $$x_2 = \frac{b - \sqrt{b^2 - 4c}}{2} $$
The above statement is equivalent to $$2^n \,\big| \, 2^n\big({x_1}^n + {x_2}^n \big) $$
