Course contentsShow
← Computer Science
Lesson 88 of 2,8722. Discrete Mathematics for CSFree lesson

Inductive Hypothesis

Formulating the assumption that the statement holds for an arbitrary n=k in the inductive step.

Inductive Hypothesis

You'll learn: How to formulate the assumption that a statement holds for an arbitrary case n=k in the inductive step of a proof by mathematical induction.

What Is the Inductive Hypothesis?

When proving statements using mathematical induction, you've already established the Base Case (showing the statement is true for the first value, usually n=0 or n=1). The next crucial step is the Inductive Hypothesis—this is where you assume the statement is true for some arbitrary value n=k.

Think of it like climbing an infinite ladder: you've proven you can stand on the first rung (base case). Now you need to show that if you're standing on any arbitrary rung k, you can reach rung k+1. The inductive hypothesis is the "if I'm on rung k" part—you temporarily assume you're there.

Formulating the Hypothesis

The inductive hypothesis is written as an assumption:

"Assume the statement P(n) is true for n=k."

For example, if you're proving that the sum 1 + 2 + 3 + ... + n = n(n+1)/2, your inductive hypothesis would be:

"Assume that 1 + 2 + 3 + ... + k = k(k+1)/2 for some arbitrary integer k ≥ 1."

You're not proving this assumption—you're stating it as a temporary given. This assumption becomes the foundation for the next step (the inductive step), where you'll prove the statement holds for n=k+1.

Why It Matters

The inductive hypothesis bridges your base case to all subsequent cases. Without it, you have no logical connection to extend the truth from one case to the next.

Key Takeaway: The inductive hypothesis is the assumption that statement P(n) holds for an arbitrary n=k; it's the "if" part that lets you prove the "then" (that P(k+1) also holds).