# Proof of binomial coeffient

• Feb 25th 2007, 08:10 AM
luckyc1423
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
• Feb 25th 2007, 12:49 PM
ThePerfectHacker
Quote:

Originally Posted by luckyc1423

• Feb 25th 2007, 01:57 PM
Jhevon
Quote:

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
• Feb 25th 2007, 02:17 PM
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!!
• Feb 25th 2007, 02:21 PM
Jhevon
Quote:

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