Proving P(n) for nCr Using Induction: A Step-by-Step Guide

  • Thread starter soulflyfgm
  • Start date
  • Tags
    Induction
In summary, the conversation discusses the statement P(n) that for any natural number n, the combination nCr is also a natural number for every r with 0<= r<= n. It is proven that nC0 and nCn are integers, and the identity (n+1)Cr = nCr +nC(r-1) is used to show that nCr is a natural number for all n and all r. However, it is noted that 0C0 is actually equal to 1, not 0.
  • #1
soulflyfgm
28
0
i have this so far..please tell me if this is right..do u think this prove is correct

Let P(n) be the statement that for any n in the natural numbers N, nCr is an element of N for every r with 0<= r<= n
nCr = n!/(r!(n-r)!)
0Cr = o!/(r!(0-r)!) = 0( here i don't know wat r is..im guessing r has to be 0 because of the 0<= r<= n)

so P(0)E(belongs) in N (natural numbers)
Suppose P(n) is a natural number of any N
then since {n+1}Cr = nCr + nC{r-1} is true ( already proved it algebraically and i will add it to this part) so it follows that the {n+1}Cr are natural numbers for all n. Hence, by inducion, nCr is a natural number for all n and all r.

can some one review this prove and tell me if its right? thank you so much for ur help
 
Physics news on Phys.org
  • #2
0C0 is 1, not 0. apart from that your idea is correct, though you also need to note that nC0 and nCn are integers, otherwise the identity you've written down

(n+1)Cr = nCr +nC(r-1)

is no help if r=n+1 or 0 then one of the terms on the left is undefined (by you).
 

What is the purpose of proving P(n) for nCr using induction?

The purpose of proving P(n) for nCr using induction is to demonstrate that a given statement or formula is true for all possible values of n. This can help to establish the validity of a mathematical argument or theory.

What is the process for proving P(n) for nCr using induction?

The process for proving P(n) for nCr using induction involves three steps: the base case, the inductive hypothesis, and the inductive step. The base case establishes that the statement is true for the first value of n (usually n=1). The inductive hypothesis assumes that the statement is true for some arbitrary value of n (usually k). And the inductive step proves that if the statement is true for k, then it must also be true for k+1. By repeating this process, we can show that the statement is true for all possible values of n.

What is the significance of using induction to prove P(n) for nCr?

Using induction to prove P(n) for nCr is significant because it provides a rigorous and systematic approach to proving mathematical statements. It allows us to prove a statement for an infinite number of values without having to test each one individually. This method is widely accepted and used in mathematical proofs and is considered a powerful tool for establishing the validity of mathematical arguments.

What are some common mistakes to avoid when using induction to prove P(n) for nCr?

Some common mistakes to avoid when using induction to prove P(n) for nCr include: not clearly stating the base case, not properly formulating the inductive hypothesis, and making incorrect assumptions in the inductive step. It is also important to ensure that the statement being proved is actually true for the base case and that the inductive step is logically sound. It is always a good idea to double-check all steps and assumptions in the proof to avoid errors.

Can induction be used to prove P(n) for nCr for all values of n, including negative and non-integer values?

No, induction can only be used to prove statements for positive integer values of n. This is because the inductive step relies on the statement being true for the previous value of n, and there is no previous value for negative or non-integer values. Additionally, the base case can only be established for positive integer values. Therefore, induction is not applicable for proving P(n) for nCr for all values of n.

Similar threads

Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
576
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
514
Prove ##a + b = b + a## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
813
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
521
Direct Proof that every zero of p(T) is an eigenvalue of T
    • Calculus and Beyond Homework Help
Replies
24
Views
795
How to show that these sequences are summable?
    • Calculus and Beyond Homework Help
Replies
1
Views
255
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
504
Integral of x^n using Reimann sums
    • Calculus and Beyond Homework Help
Replies
4
Views
653
Proofs By Induction: Proving P(n) for All n
    • Calculus and Beyond Homework Help
Replies
3
Views
1K
Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
    • Calculus and Beyond Homework Help
Replies
3
Views
549

Hot Threads

Recent Insights

Back
Top