# 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?

• Here's an observation: you can consider this as being the sum of powers of two conjugate solutions to a quadratic equation. – Cameron Williams Dec 24 '14 at 0:50
• Exactly! How do I go about proving it ? $$x^2 - bx + c = 0$$ – pooja Dec 24 '14 at 0:51
• What do you consider a non-inductive proof? Since you've got a statement of the form 'for all $n$', it's very likely that induction is going to come in eventually in one form or another... – Steven Stadnicki Dec 24 '14 at 1:02
• @pooja, if you do not start a comment with an at sign before the person's name, they will not be notified and may or may not check back and see your comment. – Will Jagy Dec 24 '14 at 1:12
• I'm not familiar enough with binomial identities. But perhaps someone else is and this could help. If $n$ is even the result using a binomial expansion is $$\sum_{k=0}^{n/2}{2n\choose 2k}(b^2)^{(n-k)}(b^2-4ac)^{k}$$ – David Peterson Dec 24 '14 at 2:55

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.

• The main induction is actually in the observation that $\Bbb P^n$ has integer entries. – Brian M. Scott Dec 24 '14 at 3:11
• @Brian You're right; there are many inductions lurking here. The one you point to comes down to asserting that the integers are closed under addition and multiplication. I'll accept that as immediately obvious. The crux of the matter, though, is that scalars commute with matrices, whence $(2\mathbb P)^n = 2^n \mathbb P^n$: that shows where the powers of $2$ come from. – whuber Dec 24 '14 at 4:09
• Fascinating how people's intuitions differ: my intuitive reaction is just the opposite. I see the fact that scalars commute with matrices as more obvious than the fact that an integer matrix has integer powers. – Brian M. Scott Dec 24 '14 at 4:43
• Note, you've got $\sqrt{b^2-4c^2}$ when the original question asked about $\sqrt{b^2-4c}$. – Thomas Andrews Dec 28 '14 at 3:13
• @Thank you for noticing that, Thomas. That is easily fixed by replacing one of the $c$'s by $1$; I will make the change. – whuber Dec 28 '14 at 16:53

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

• You can divide $a_n$ by $2^n$ and note that the terms of the recurrence relations are still integers. This implies that $\frac{a_n}{2^n}$ is an integer for all $n$, which is arguably an induction step but a wholly trivial one... – Steven Stadnicki Dec 24 '14 at 0:56
• @StevenStadnicki: nice touch. – Jack D'Aurizio Dec 24 '14 at 0:57
• Yes I have the exact same proof. I am only looking for non-induction proof here if it is possible. Thanks you though :) – pooja Dec 24 '14 at 0:57

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}.$$

• Don't you still have to show that the remainder after dividing through by $2^n$ is an integer? – Cameron Williams Dec 24 '14 at 1:57
• @Cameron Yes, but since now I can't spend longer on that, I hoped the OP would be somewhat satisfied / someone else would do it. – Vincenzo Oliva Dec 24 '14 at 2:04

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)$$

• Which helps only if you know that $x_1^n+x_2^n$ is an integer... – Thomas Andrews Dec 28 '14 at 3:14
• Which can be proven using induction. I realize that's not what the asker wanted, but it works. – Dylan Dec 28 '14 at 3:15