0
$\begingroup$

I'm trying to understand how to use induction to prove a claim not for every natural number $n$, but only for specific natural numbers, say $0 \leq n \leq k$ for some positive $k$.

After proving $P(0)$, does it make sense to assume the proposition is true for $P(n)$ when $0 \leq n \leq k - 1$? In this way, I won't have to consider $n = k + 1$, and I believe the proof follows for all such $n$.

$\endgroup$
1
  • 1
    $\begingroup$ Yes, you can use strong induction, but you need to show the induction step nevertheless, namely $P(k)$. $\endgroup$ Commented Dec 31, 2023 at 9:59

1 Answer 1

1
$\begingroup$

Let the property $Q$ be defined as $Q(n)=P(n)$ for $n\leq k$ and $Q(n)=\text{true}$ for $n> k$. Then showing that $Q$ is true for all $n$ is equivalent to show that $P(n)$ is true for all $n\leq k$. Now proving $Q(n)$ to be true for all $n$ by induction obviously means that

  1. $P(0)$ has to be true and
  2. P(n+1) is true provided that $P(n)$ is true for all $ n\leq k-1$.

So this justifies your idea of proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .