How to prove that $2(2\sqrt2)^n\cos(n \cdot \arctan(\frac{\sqrt 7}{5}))$ is an odd integer for every $n \in \Bbb N$? I was learning proof by induction and stumbled up on this problem:
Let $p$ and $q$ be complex numbers such that  $p+q=5$  and $p^2+q^2=9$. Prove that $p^n + q^n$
is an odd integer for every $n \in \Bbb N$.
I solved the system of equations and got that $p$ and $q$ are complex conjugate numbers ($p = \frac{5}{2} \pm \frac{\sqrt 7}{2}i$ and $q = \frac{5}{2} \mp \frac{\sqrt 7}{2}i$)
I was able to reduce it to this expression:
$2(2\sqrt2)^n\cos(n \cdot \arctan(\frac{\sqrt 7}{5}))$
using the polar form of a complex number.
But now I don't know how to proceed. How to prove that $2(2\sqrt2)^n\cos(n \cdot \arctan(\frac{\sqrt 7}{5}))$ is an odd integer for every $n\in \Bbb N$. Can anyone please help me?
 A: That's not the way to do this.
First find $pq = ((p+q)^2 - (p^2 + q^2))/2$, then note that
$$ p^{n+1} + q^{n+1} - (p+q)(p^n + q^n) = - q p^n - p q^n = - p q (p^{n-1} + q^{n-1}) $$
And then use induction.
A: Solving for $p$ and $q$ explicitly does not help us. Here we can show off the power of induction.
Our base case is actually two equations: $p^1+q^1=5$ and $p^2+q^2=9$ are a given. Also what helps is that
$$\begin{cases}p+q=5\\p^2+q^2=9\end{cases}\implies pq=8$$
Next, our inductive hypothesis: Assume that $p^{n-1}+q^{n-1}$ and $p^n+q^n$ are odd integers. Then
$$(p+q)(p^n+q^n) = (p^{n+1}+q^{n+1})+pq(p^{n-1}+q^{n-1})$$
By our assumptions, the product of the LHS is an odd integer, so should be the RHS. The term $pq(p^{n-1}+q^{n-1})$ is even, which implies that $p^{n+1}+q^{n+1}$ is odd.
Since we had $p^n+q^n$ odd by assumption, we have successfully proved that $p^{n-1}+q^{n-1}$ and $p^n+q^n$ being odd (our $n$th statement) implies that $p^n+q^n$ and $p^{n+1}+q^{n+1}$ are odd, too (our $(n+1)$th statement). Thus we have successfully proved that $p^n+q^n$ is odd for all $n$.
A: HINT:
$$ p^{n+1}+q^{n+1}=(p+q)(p^{n}+q^{n})-pq(p^{n-1}+q^{n-1}) $$
Use the above identity to prove your case by induction.
A: I think you're making the original problem too difficult. If we're trying to do proof by induction, we need to prove a base case and an inductive step. The base case(s) are already given to us since $p^n + q^n$ is an odd integer for $n = 1, 2$. Now, we just need to prove it more generally. Assume that the result holds for for $n \leq k$ (strong induction assumption), and consider the case $n = k+1$:
$$
p^{k+1} + q^{k+1} = p(p^k + q^k) - pq^k + q(p^k + q^k) - q p^k\\
= (p + q)[p^k + q^k] - pq[p^{k-1} + q^{k-1}]
$$
We know from the strong induction assumption that $p + q$, $p^k + q^k$ and $p^{k-1} + q^{k-1}$ are all odd integers. Let us now determine what $pq$ is equal to. As you have already solved the system of equations, I will use your result to get:
$$
pq = \left(\frac{5}{2} + \frac{\sqrt{7}i}{2} \right)\left(\frac{5}{2} - \frac{\sqrt{7}i}{2} \right) = \frac{25}{4} + \frac{7}{4} = \frac{32}{4} = 8
$$
Thus, we have
$$
p^{k+1} + q^{k+1} = [odd] * [odd] + [even] * [odd] = odd \quad \square
$$
A: To solve your original problem.
Let
$r_n=p^n+q^n
$.
$\begin{array}\\
r_n(p+q)
&=(p^n+q^n)(p+q)\\
&=p^{n+1}+p^nq+q^np+q^{n+1}\\
&=p^{n+1}+q^{n+1}+p^nq+q^np\\
&=r_{n+1}+pq(q^{n-1}+p^{n-1})\\
&=r_{n+1}+pqr_{n-1}\\
\end{array}
$
so
$r_{n+1}
=r_n(p+q)-pqr_{n-1}
$.
In this case,
$p+q=5$
is odd
and
$25
=(p+q)^2
=p^2+q^2+2pq
=9+2pq
$
so
$pq=(25-9)/2
=8$
is even.
(This corrects an error in my previous version.)
Therefore
if $r_n$ and
$r_{n-1}$ are both odd
then
$r_n(p+q)$ is odd
(since both $r_n$
and $p+q$ are)
and
$pqr_{n-1}$ is even,
so $r_{n+1}$ is odd,
being the sum of an odd
and even number.
