Difference of induction and divide and conquer

Question

I have seen that induction and divide and conquer are used as problem solving techniques but they are treated either as something different or the former as a way to support the latter.

To me it seems that they are both exactly the same thing i.e. defining the problem in a way that has (can be composed of) smaller instances of the same original problem, having a base case and a way to build a solution for instance $n + 1$ having the solution to instance $n$.
So in my understanding they (induction and divide and conquer) are exactly the same thing/exactly the same problem solving approach or at least different terms for the same thing/topic.

Am I misunderstanding something? If yes what is the difference I am overlooking? If not why are they treated as different things in texts?

Answer 1

They are somewhat related concepts, but not the same. Induction is a way of proving something by building up from smaller cases. "Divide and conquer" is an approach to solving a problem (which may be a proof).

Not all induction problems can be described as divide and conquer. For example, there are any number of arithmetic statements like $\sum_{i=1}^n i = \frac{n(n+1)}2$ that can be proved by induction, but these proofs wouldn't be considered divide and conquer since you're just incrementally adding one more element at a time. Usually, "divide and conquer" suggests splitting up the problem into chunks (e.g., halves or thirds).

On the other hand, not all divide and conquer approaches are instances of induction. Maybe you're trying to find a path visiting different delivery locations in a city (the Travelling Salesman Problem): you might break this down into neighbourhoods, then break it down again as needed, solve the smaller problems, then recombine them. But the result will not necessarily be optimal, and notably this wasn't part of a proof, just an approach to a problem.

Answer 2

They're related, but different. When you prove, by induction on $n$, the complexity (be it in time or memory) of a recursive algorithm for solving a size-$n$ problem, divide and conquer as a definition of that recursive algorithm proves a recurrence relation used in the inductive step.

For example, this algorithm for the tower of Hanoi takes $T_n$ movements with $n$ discs with $T_0=0$, and divide and conquer proves $T_{k+1}=2T_k+1$, allowing us to prove by induction $T_n=2^n-1$.

Note that divide and conquer can also be used to prove approximations, asymptotic behaviours, and bounds for the complexity; see here and here.