Prove by careful induction that if $r \in \mathbb{N}$, then $$b^{2^r} - 1 = (b-1)(b+1)(b^2 + 1)(b^{2^{2}} + 1) ... (b^{2^{r-1}} + 1)$$

I'm a bit rusty on Mathematical inductions, and I'm getting stuck in the process. Here's what I've tried so far:

To begin, proceed by induction on $r$

Base case: $r=1$:

$b^2 - 1 = (b-1)(b+1) = b^2 + b - b - 1 = b^2 -1$

So the base case holds.

Inductive hypothesis: the theorem holds for all $r=k$

Inductive step: let $r=k+1$

$b^{2^{k+1}} = (b-1)(b+1) ... (b^{2^{k+1-1}})$

I'm not sure this is even right so far, or where I need to go from here.

  • $\begingroup$ Since this is the second time I see it in a post of yours what's the meaning or point of careful in careful induction. $\endgroup$
    – quid
    Sep 8 '16 at 19:12
  • 1
    $\begingroup$ Good question. Not exactly sure myself, but I think it just means to pay close attention to the steps. I don't think it means anything special like strong induction. $\endgroup$
    – kojak
    Sep 8 '16 at 19:28

For the inductive step, you assume

$$b^{2^k} - 1 = (b-1)(b+1)(b^2 + 1)(b^{2^{2}} + 1) ... (b^{2^{k-1}} + 1)$$ and you want to prove $$b^{2^{k+1}} - 1 = (b-1)(b+1)(b^2 + 1)(b^{2^{2}} + 1) ... (b^{2^{k-1}} + 1)(b^{2^{k}} + 1).$$

Using the inductive hypothesis, you know that the product of all but the last bracket is $b^{2^k}-1$. So it remains to check $$b^{2^{k+1}} - 1 =(b^{2^k}-1)(b^{2^k}+1)$$ which is true by difference of squares, completing the inductive step.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.