# Thread: Proof of binomial coeffient

1. ## Proof of binomial coeffient

Problem 1:
Define the binomial coefficient
n by
r

n = n! / (r!(n-r)!) for r = 0,1,2,...., n
r

problem: show that
n
r

+

n
r-1

=
n+1
r

for r = 0,1,2,...,n

problem 2:
Use induction to prove Bernoulli's inequality:
If 1+x>0, then (1+x)^n >= 1+nx for all n (element) of N

N is the set of positive integers, natural numbers

2. Originally Posted by luckyc1423

3. Originally Posted by luckyc1423
Problem 1:
Define the binomial coefficient
n by
r

n = n! / (r!(n-r)!) for r = 0,1,2,...., n
r

problem: show that
n
r

+

n
r-1

=
n+1
r

for r = 0,1,2,...,n

problem 2:
Use induction to prove Bernoulli's inequality:
If 1+x>0, then (1+x)^n >= 1+nx for all n (element) of N

N is the set of positive integers, natural numbers
For problem 2:

If 1 + x > 0 then (1 + x)^n >= 1 + nx for all n.

Since 1 + x > 0, x > -1. So n*x^2 is nonnegative for all n in N and x in R.

Now we show by induction that (1 + x)^n >= 1 + nx for all n

Let P(n) be (1 + x)^n >= 1 + nx for all n.

=> P(1): (1 + x)^1 >= 1 + 1*x, which is true.
Since P(1) is true, assume P(n) is true. We show P(n) => P(n+1)

Now (1 + x)^(n + 1) = (1 + x)*(1 + x)^n
>= (1 + x)(1 + nx)
= 1 + x + nx + nx^2
= 1 + (1 + n)x + nx^2
>= 1 + (1 + n)x since nx^2 is nonnegative.

Thus we have (1 + x)^(n + 1) >= 1 + (n + 1)x which is P(n + 1). So since P(n + 1) is true, we can conclude that P(n) is true for all n. That is, (1 + x)^n >= 1 + nx for all n

4. I had half of this problem done, I am starting to grasp the concept some....keep up the good work and help, good luck with your class!!

5. Originally Posted by luckyc1423
I had half of this problem done, I am starting to grasp the concept some....keep up the good work and help, good luck with your class!!
Yeah, it's always the same principle, (with some variations for more complicated problems).

You have a statement P(n) you want to prove for all n. You begin by showing P(1) is true. If it is, you assume P(n) is true, and then show that P(n + 1) is true as a consequence of P(n) being true.

Variations are usually in the first step. For example, for a class i had last year, i had to show up to P(5) was true before i could solve the problem.

Thanks for the well wishes, i'll need them. good luck with your classes as well