0 like 0 dislike
0 like 0 dislike
[Induction] Could you check if this inductive proof is correct? (binomial coefficients)

2 Answers

0 like 0 dislike
0 like 0 dislike
It’s fine. But in (3) you also need for p=n+1 since your IH requires p at most n.
0 like 0 dislike
0 like 0 dislike
This looks basically correct to me. The part you're worried about can be made a little more precise if you like, as follows:

The statement you're actually trying to prove is

∀n∈ℕ∀p∈{p∈ℕ:0≤p≤n}: nCp∈ℕ.

You prove this by induction on n, so the proposition in question is

P(n) = "∀p∈{p∈ℕ:0≤p≤n}: nCp∈ℕ".

Your base case is fine. At the induction hypothesis, you simply assume P(n). This isn't strong induction; you only need to assume a single case.

Then at the induction step, you use P(n) twice: once to show that nC(p-1) is natural, and once to show that nCp is.

Incidentally, there is one more nitpick you have to worry about: when p=n+1, you can't use the induction hypothesis because nC(n+1) doesn't even make sense. Instead, you have to handle this case separately by showing that (n+1)C(n+1) is natural.

Related questions

0 like 0 dislike
0 like 0 dislike
5 answers
WinnieTeca asked Jun 21
My understanding is that t-tests work mainly because sampling distributions of means are normally distributed—regardless of the distribution of the variable under study...
WinnieTeca asked Jun 21
0 like 0 dislike
0 like 0 dislike
7 answers
kajhendriks asked Jun 21
I'm talking about notation that I see in my stats book that looks like the notation here: https://en.wikipedia.org/wiki/Probability_density_function#Absolutely_continuous...
kajhendriks asked Jun 21
0 like 0 dislike
0 like 0 dislike
5 answers
DasmanNewsCom asked Jun 21
For those who passed SRM and sat for PA not long after, how long did you need to study for PA to feel prepared?
DasmanNewsCom asked Jun 21
0 like 0 dislike
0 like 0 dislike
3 answers
ericdanetz asked Jun 21
Health to Life switchers, could you tell me some reasons why you switched and what makes you more interested in Life compared to Health?
ericdanetz asked Jun 21
0 like 0 dislike
0 like 0 dislike
19 answers
chorleyfc asked Jun 21
What do you do after an exam without instant results?
chorleyfc asked Jun 21

33.4k questions

135k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!