Using strong induction to prove divisibility statements

Question

I need to prove that for $n \in \mathbb{N}$ odd, $a,b \in \mathbb{Z}$, $a \neq b$, $a+b \ | \ a^n + b^n$.

Does this require strong induction on $n$?

$$p(n) = \{ n\in \mathbb{N} : a +b \ | \ a^{2n-1} + b^{2n-1} \}$$

The base case ($n=1$) checks out. I'd then have to try to prove that if $p(k)$ is true for $k <n+1$, $p(n+1)$.

$$ a +b \ | \ a^{2n-1} + b^{2n-1} \iff a +b \ | \ (a^{2n-1} + b^{2n-1})(a^2 + b^2) = a^{2n+1} + b^{2n+1} + (a^2b^2)(a^{2n-3} + b^{2n-3})$$

Since by assumption $ a +b \ | \ a^{2n-3} + b^{2n-3}$, we have that $ a +b \ | \ a^{2n+1} + b^{2n+1}$.

Is this reasoning correct?

Answer 1

Looks OK to me.

I would have written $$ \ (a^{2n-1} + b^{2n-1})(a^2 + b^2) = a^{2n+1} + b^{2n+1} + (a^2b^2)(a^{2n-3} + b^{2n-3}) $$ as $$a^{2n+1} + b^{2n+1}= (a^{2n-1} + b^{2n-1})(a^2 + b^2) - (a^2b^2)(a^{2n-3} + b^{2n-3}) $$ to make it clear that, if $(a+b)|(a^{2k-1}+b^{2k-1})$ for $k = n$ and $k=n-1$ then it does for $k=n+1$.

I would call this "slightly strong" induction, since it requires the induction hypothesis to be true for $n$ and $n-1$ (or, in general, for a bounded number of cases) to show that it is true for $n+1$.

If the induction hypothesis needs to be true for an unbounded number of previous cases, then I consider that to be "quite strong" induction.

Answer 2

First off, be careful here:

$$a + b \mid a^{2n-1} + b^{2n-1} \iff a +b \mid (a^{2n-1} + b^{2n-1})(a^2 + b^2).$$

I can see how the $\implies$ direction holds, but not the $\impliedby$ direction holds. The implication $x \mid yz \implies x \mid y$ can hold under certain additional assumptions, such as when $\operatorname{gcd}(x, z) = 1$, but I'm not aware of such a condition that necessarily holds in this case. Fortunately, this doesn't seem to be a big problem.

According to your algebra, we have $$a^{2n + 1} + b^{2n + 1} = (a^2 + b^2)(a^{2n - 1} + b^{2n - 1}) - a^2b^2(a^{2n - 3} + b^{2n - 3}).$$ If we assume that $a + b$ divides $a^{2n - 1} + b^{2n - 1}$ and $a^{2n - 3} + b^{2n - 3}$, then it must divide the left hand side as well.

Because we are assuming exactly two previous cases, it is important to establish two base cases. Think about it this way: normally induction works intuitively by proving the first case, then using the first case to prove the second case, using the second case to prove the third case, etc. The inductive step is supposed to give you the template for using one case to prove the next.

However, in your proof, how can we use the $n = 1$ case to prove the $n = 2$ case? According to the argument presented, $$a^3 + b^3 = (a^2 + b^2)(a + b) - a^2 b^2(a^{-1} + b^{-1}),$$ which is not an expression of integers! Sure, it can be modified to become an expression of integers, but it needs special treatment. Since your inductive step draws on two steps previous, you had better make certain that you have two cases proven.

So, note that $a + b \mid a + b$ trivially and $a + b \mid a^3 + b^3$, as $a^3 + b^3 = (a + b)(a^2 - ab + b^2)$, and the rest follows by induction.