How many Assumptions can I make in Proof by Induction?

Question

Let's say I want to prove by mathematical induction that a statement involving $n$ is true for all $n\in\mathbb N$. A classic example is proving that $$\sum_{r=1}^nr=\frac{1}{2}n(n+1)$$ The base step is trivial. This requires only $1$ assumption to prove by induction; namely that for a given $n=k$ the statement holds and then we go on to prove that this implies the statement is also true for $n=k+1$. But what if one assumption is not enough to prove the general case? Let's say to prove the general case I needed to assume the statement held for $2$ values: $n=k-1$ and $n=k$ and then I used this to prove that the result follows for $n=k+1$. Would that be ok?

More generally, for a proof by induction must I only make one assumption or am I permitted to use many? Please explain why, whatever the answer is.

Thank you for your help.

Answer 1

Of course you can! But then you must have two base cases. For example, if you show that ${n=k}$ and ${n=k+1}$ both being true would imply that ${n=k+2}$ is true, and you have two base cases (such as ${n=0}$ and ${n=1}$ for example) then that would imply the case for ${n=2}$ is true. Then it being true for ${n=1}$ and ${n=2}$ would imply it's true for ${n=3}$. Then for $4$, then for $5$... etc etc. It's the same principle

Answer 2

Just to complement the above answer, there is a form of induction called "course-of-values" or "complete" or "strong" induction that requires no base cases. It says that to prove $P(n)$ for all $n$, it is sufficient to prove that for all $n$, $P(n)$ holds, if $P(m)$ holds for all $m < n$. In symbols: $$ (\forall n ((\forall m < n P(m)) \Rightarrow P(n))) \Rightarrow (\forall n P(n)) $$ You can use this, for example, to prove that any natural number $n > 1$ is a product of primes. (This form of induction sneaks the base case in secretly because "$\forall m < n P(m)$" is automatically true when $n = 0$).

Answer 3

There's no upper limit on how many base cases you are allowed to use, although too many can be unnecessary and more than you need. The way to tell how many cases you need is to formulate your problem as a recurrence relation. For example, your given series can be represented as $$a_{n+1}=a_n+(n+1)$$ with $a_1=1$. The number of $a_k$ terms on the RHS of the recurrence equation represents the number of base cases you need to solve any such recurrence relation.

Answer 4

I found a webpage talking about different type of Induction.
You maybe looking for Second Principle of Mathematical Induction, which make multiple assumptions.