# Explain what is wrong with the following “proof” by induction.

Basically, there's so much going on in this problem that I don't even understand it. I've read it about one million times, but it still isn't making sense to me. Any hints would be appreciated...

Claim: Let $p$ be a polynomial of degree $n ≥ 1$ that is a product of the form $$p(x) = ax(a_1x + b_1)(a_2x + b_2). . .(a_{n−1}x + b_{n−1}), \text{where } a, a_i , b_i ∈ R$$

Then if $p(c) = 0$ we must have $c = 0$.

“Proof”: Note that because the degree is $n$ the product $aa_1 . . . a_{n−1}$ is nonzero. We attempt to prove this by induction on $n$. The base case is when $n = 1$. In that case $p(x) = ax$, and, because $a\neq 0$, $p(c) = ac = 0$ implies $c = 0$. Therefore $P(1)$ holds. Now suppose that $P(n)$ holds for some $n ∈ N^+$, and let $p$ be a polynomial of degree $n+ 1$ that has the form $p(x) = ax(a_1x + b_1). . .(a_nx + b_n)$. We must show that if $p(c) = 0$ then $c = 0$. But if $p(c) = 0$ then $0 = p(c) = ac(a_1c + b_1). . .(a_nc + b_n)$. One of the factors $ac, a_1c+b_1, . . . , a_nc+b_n$ must vanish. Rearranging terms if necessary we may suppose that either $ac = 0$ or $(a_1c + b) = 0$. Hence the product $ac(a_1c + b) = 0$. Now $q(x) = ac(a_1c + b_1). . .(a_{n−1}c + b_{n−1})$ is a polynomial of degree $n$ of the form we are considering. Since $ac(a_1c + b) = 0$, we have $q(c) = 0$. Therefore by the inductive hypothesis (i.e. by $P(n)$), we must have $c = 0$. Therefore $p(c) = 0$ implies that $c = 0$, which completes the inductive proof of the claim.

• Not sure I quite follow your argument, but it seems to break down at the n=2 case, a bit like the famous "all horses are the same color" theorem. – John Brevik Mar 4 '15 at 2:06
• Actually, $q(x)$ is a constant polynomial in $x$, not a polynomial of degree $n$, so the inductive hypothesis does not apply. All you get is that $ac(a_1c + b_1). . .(a_{n−1}c + b_{n−1}) = 0.$ – rogerl Mar 4 '15 at 2:06
• I'm sorry but I just don't see why $P(c)=0$ should imply $c=0$. What if $c=-\frac{b_i}{a_i}$? – Tim Raczkowski Mar 4 '15 at 2:07
• You're assuming that $a_1c+b_1\neq a_{n-1}c+b_{n-1}$. However, when $n=2$, these are the exact same term! – Akiva Weinberger Mar 4 '15 at 2:34

The problem is that $P(1)$ doesn't imply $P(2)$ by that argument. In fact, the fallacy lies in the following: "Rearranging terms if necessary we may suppose that..."
In the case $n=2$; say, you have $ax(bx+d)=0$. This implies $ax=0$ or $bx+d=0$ but these conditions are not symmetric, i.e. you're not covering all cases when you say "...we may suppose."