# Question Regarding an Induction Proof from (Principle of Mathematical Induction, Chapter 4 in the NCERT Textbook)

This is a small doubt regarding a question from the NCERT exemplar questions on the chapter Principle of Mathematical Induction (actually it's a deleted chapter in the sense that it's been eliminated from the syllabus that the CBSE had devised for the current year, alongside Binomial Theorem and Mathematical Reasoning). I tried to do this one question and would like to verify if the methodology I used was right.

A series starts with its first term $$b_0 = 5$$ and progresses as $$b_k = b_{k-1}+4$$. Prove that the elements of the series are of the form $$5 + 4n$$ for all natural number $$n$$.

I did as follows: Let $$S = \lbrace b_n:b_0 = 5, b_n = b_{n-1} + 4, n \in \mathbb{N}\rbrace$$
Let $$P(k) = 5+4k \in S$$
Base case: We see that $$P(1)$$ is true ($$9 \in S$$) and also $$P(2)$$ also holds true ($$13 \in S$$)
Inductive step: Let's assume that this holds for all $$1\leq n \leq k \implies P(k)$$ is true and hence $$5 + 4k \in S$$, so we can safely assume $$b_k = 5+4k$$
We see, $$5 + 4(k+1) = \underline{5+4k} + 4 = b_k + 4$$ which essentially turns out to be $$b_{k+1}$$ and thus we see, $$5+4(k+1) = b_{k+1} \in S$$ and hence $$P(k+1)$$ is also true.
Thus we see that $$b_n = 5 + 4n \space \forall\space n \in \mathbb{N}$$.

I haven't tried this sort of a proof before so I'd like to learn from you what is wrong with the proof, what assumptions are actually not worth doing or are dangerous to add fallacies/loopholes to the proof.

• This is an absolutely fine proof. Sep 19 at 15:36
• you are mixing up k and n. The question is written poorly, but it seems to me that the thing they want you to prove by induction is that for all natural numbers k you have $b_k = 5 + 4k$, so "P(n)" would be $b_n = 5+4n$ (and the base case should be P(0), not P(1)). Sep 19 at 15:43
• You're free to use any variable name you want, but "P(n) = 5+4k" will be wrong whatever you choose :). But if you don't think 0 is a natural number then the question isn't correct, since one of the terms is 5. Sep 19 at 15:47
• @MatthewTowers omg... thanks a lot sir!!! I have noticed it now... How careless of me! Sep 19 at 16:06
• @Spectre I understand and appreciate that your preoccupations are also turned to others, this is so important to have this attitude ! Sep 20 at 6:32

## 2 Answers

Critiques.

My first critique is were the Proposition states "the elements of the series are of the form 5+4n for all natural number n" and you state "Let $$P(n) = 5+4k \in S$$"

I don't think the wording of the proposition is very clear. ""the elements of the series are of the form 5+4n" would mean that for every $$b_k$$ there is an $$n$$ so that $$b_k = 5+4n$$. But the clause "for all natural number n" muddles it. Are the saying for every natural $$n$$ there is $$k$$ so that $$5+4n=b_k$$? So are the saying that the set $$\{b_k\}$$ and the set of all $$\{5+4n|n\in \mathbb N\}$$ are the same set (possibly with some doubling up)?

It'd have been a lot more straightforword (and easier to prove) if the proposition had been that stronger (and still true) statment that for every $$n\in \mathbb N$$ we have $$b_n = 5+ 4n$$. But the proposition didn't say that. As best I can intepret it the proposition says "For every $$n \in \mathbb N$$ then $$5+4n \in S$$ and for ever $$b_k\in S$$ then $$b_k = 5+4n$$ for some $$n\in \mathbb N$$". That is two things to prove.

(This is the books fault not yours.)

Your statement: $$P(n) = 5+4k \in S$$ is hard to parse. It take it you mean: The statement $$P(n)$$ is $$5+4k \in S$$. But the variables $$n$$ and $$k$$ don't agree. I'll take it you mean for all $$n \in \mathbb N$$ that $$5+4n\in S$$ so $$P(N):: 5+4n \in S$$ would be what you mean.

But this is only half the statement. Proving $$P(n)$$ for all $$n$$ would show us $$\{5+4n|n\in \mathbb N\}\subset S$$.

The other half would be $$Q(n):: b_n = 5+4k$$ for some natural number $$k$$ and proving that will prove $$S \subset \{5+4n|n\in \mathbb N\}$$. Together that proves $$S = \{5+4n|n\in \mathbb N\}$$.

But.... this is ridiculous.....

We should just state: We are going to prove $$P(n)::b_n = 5 + 4n$$ for all $$n\in \mathbb N$$. That is what you proved in the end anyway....

....

Now your proof:

"We see that P(1) is true (9∈S) and also P(2) also holds true (13∈S)"

Okay, maybe we should point out that $$5 + 4\cdot 1 = 9$$ and $$9\in S$$ because $$b_1 = b_0 + 4 = 5 + 4=9$$; and that $$5+4\cdot 2 = 13$$ and $$13\in S$$ becase $$b_2 = b_1+4 = 9 + 4 = 13$$-- just to be clear, but yes, that is correct.

"Inductive step: Let's assume that this holds for all 1≤n≤k⟹P(k) is true and hence 5+4k∈S, so we can safely assume $$b_k=5+4k$$"

Ah, see! But your proposition was never that $$5 + 4k = b_k$$. Your proposition was that $$5 + 4k\in S$$. Maybe $$5 + 4\cdot 87 = b_{153}$$..... But you know what.... I blame your text, not you, it's pretty clear that proving $$b_k= 5+4k$$ is a stronger and true statement.

(FWIW.... if I wanted to prove $$5+4k \in S \implies 5+4(k+1) \in S$$ without assuming that $$5+4k = b_k$$ we could do this: If $$5+4k \in S$$ then there is a $$b_m$$ so that $$b_m = 5+4k$$. Therefore $$b_{m+1} = 5+4k +4 = 5+4(k+1)$$. So $$5+4(k+1) = b_{m+1} \in S$$.... but that's .... kinda silly, isn't it... back to your proof....)

"We see, 5+4(k+1)=5+4k––––––+4=bk+4 which essentially turns out to be bk+1 and thus we see, 5+4(k+1)=bk+1∈S and hence P(k+1) is also true."

Yes, that's great. Just fine.

"Thus we see that bn=5+4n ∀ n∈N"

Okay.... If our proposition from the start had been: $$P(n):: b_n = 5+4n$$ and we had done

Induction: $$k=0$$. $$b_0 = 5 = 5+4\cdot 0$$. $$b_1 = b_0 + 4 = 5+4 = 9 = 5 + 4\cdot 1$$.

We'd be just fine.

===

FWIW if I wanted to do exactly what the book said and prove: $$5n+4\in S$$ for all $$n\in \mathbb N$$ and for all $$b_n \in S$$ then $$b_n = 5 +4k$$ for some $$k \in \mathbb N$$, I'd do

$$P(n):: 5n+4 \in S$$.

Base Case: $$n= 0$$ then $$5+4\cdot 0 =5 = b_0$$.
Induction step: $$P(k)\implies P(k+1)$$. Suppose that $$5 + 4k =b_m$$ for some $$b_m \in S$$. Then $$b_{m+1}= b_m + 4 = 5+4k + 4 = 5 + 4(k+1)$$. So $$5+4(k+1)=b_{m+1} \in S$$. So $$P(k+1)$$ is varified.

$$Q(n)::$$ every $$b_n = 5 + 4m$$ for some $$m \in \mathbb N$$.

Base Case:: $$n = 0$$. $$b_0 = 5= 5+4\cdot 0$$.
Induction Steep:: $$Q(k)\implies Q(k+1)$$
Suppose $$b_k = 5 + 4m$$. Then $$b_{k+1} = 5 + 4m + 4 = 5+4(m+1)$$ and $$m+1 \in \mathbb N$$. So $$Q(k+1)$$ is varified.

.....

But that was silly, wasn't it.

• I guess what you said in the second paragraph is perhaps what they must have asked to prove, considering the fact that questions at times come in sentences with subtle meanings XD Sep 20 at 3:11
• yeah I typed the proof up very poorly as I was in a hurry to shut the system down. I can't keep staring at my lovable machine called "a laptop" (although it's cranky at times; you may end up swearing at it if ever it turns crazy). Sep 20 at 3:15
• also I didn't check their solutions, so it's likely that I messed up with the question rather than they :D Sep 20 at 3:16
• Also, what you said wasn't so silly to defenestrate, but yeah the humorous/narrative way of your typing up is beautiful.. I feel jealous of your ability!!! :D Sep 20 at 3:17
• Don't worry... you have the gyst of the proof. Sep 20 at 6:05

There are no loopholes in this proof. It's absolutely fine. The key thing to observe before starting with this proof (and you have observed that) is to note that \begin{align*} b_n&=b_{n-1}+4\\ &=b_{n-2}+4+4\\ &=b_{n-2}+2\times 4\\ &=b_{n-3}+3\times 4\\ &\;\;\;\;\cdots\\ &\;\;\;\;\cdots\\ &\;\;\;\;\cdots\\ &=b_{n-n}+n\times 4\\ &=5+4n \end{align*}

• Thanks a lot! I was in a worry that I must have done something wrong in it as I had tried this only on simple numerical results (especially $\sqrt{n} < \sum\limits_{i=1}^{n} \frac{1}\sqrt{i}$, which I had to think a bit due to my first-time approach) Sep 19 at 15:46
• It's fine, everything has a first time approach. But, remember that if you are in CBSE board (which I assumed because you're solving NCERT), then this problem is NOT "out of syllabus" as you mentioned in the title. It's very well in your syllabus. Sep 19 at 16:05
• I mean the chapter is out of syllabus, meaning we are not asked to study it for the exams. :) Sep 19 at 16:07