Competition - post a photo you've taken of nature >>

proof by induction

Question:
Show that

\binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r}

, and prove by induction that

(1+x)^n = 1 +nx + .... + \binom{n}{r} x^r+ ....+ x^n

where

\binom{n}{r} = \frac{n!}{(n-r)!r!}

and r is positive integer, less than or equal to n.

\binom{n}{r}=\frac{n!}{(n-r)!r!}

\binom{n}{r-1}=\frac{n!}{(n-(r-1))!(r-1)!} = \frac{n!}{(n+1 -r)!(r-1)!}

\binom{n+1}{r}=\frac{(n+1)!}{(n+1 -r)! r!}

\binom{n}{r}=\frac{n!}{(n-r)!r!} + \binom{n}{r-1}

= \frac{n!}{(n-r)!r!} + \frac{n!}{(n+1 -r)!(r-1)!} = \frac{n!(n+1 -r)!(r-1)!+ n!(n-r)!r! }{(n-r)!r!(n+1 -r)!(r-1)!}= \frac{n!\left [ (n+1 -r)!(r-1)! + (n-r)!r! \right ] }{(n-r)!r!(n+1 -r)!(r-1)!}

\frac{n!\left [ [(n+1 -r)(n-r)(n-r-1)....2.1](r-1)! + [(n-r)(n-r-1)....2.1]r! \right ] }{[(n-r)(n-r-1)....2.1]r!(n+1 -r)!(r-1)!} = \frac{n!\left [ (n+1 -r)(r-1)! +r! \right ] }{r!(n+1 -r)!(r-1)!}

= \frac{n!\left [ (n+1 -r)[(r-1)(r-2)(r-3)...2.1] + (r)(r-1)(r-2)(r-3)...2.1 \right ] }{(r)!(n+1 -r)![(r-1)(r-2)(r-3)...2.1]} = \frac{n!\left [ (n+1 -r) + r \right ] }{r!(n+1 -r)!}

\frac{n!(n+1)}{r!(n+1 -r)!} = \frac{(n+1)!}{r!(n+1 -r)!}

(1+x)^n = 1 +nx + .... + \binom{n}{r} x^r+ ....+ x^n

Suppose the results hold for a particular value of n, say k ;

(1+x)^k= 1 +kx + .... + \binom{k}{r} x^r+ ....+ x^k

Then adding the next term of the series

x^{(k+1)}

on both sides;

(1+x)^k + x^(k+1)= 1 +kx + .... + \binom{k}{r} x^r+ ....+ x^k + x^{(k+1)}

So I need to proof that

(1+x)^k + x^{(k+1)} = (1+x)^ {(k+1)}

this where i have a problem

Please can i have help as I am having problems with this one how do i use proof by induction to complete the 2nd part of the question

thank you

(edited 4 years ago)

Reply 1

mqb2766

For induction on the second part you must show
(1+x)^(k+1) = (1+x)^k * (1+x) = ....
Has the right form. Its relatively straightforward given the previous result.

You do not add x^(k+1) as you seem to be saying in the last couple of lines.

Note, the first proof could be considerably simplified if you factored out the common terms at the start.

Original post by bigmansouf

Question:
Show that

\binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r}

, and prove by induction that

(1+x)^n = 1 +nx + .... + \binom{n}{r} x^r+ ....+ x^n

where

\binom{n}{r} = \frac{n!}{(n-r)!r!}

and r is positive integer, less than or equal to n.

\binom{n}{r}=\frac{n!}{(n-r)!r!}

\binom{n}{r-1}=\frac{n!}{(n-(r-1))!(r-1)!} = \frac{n!}{(n+1 -r)!(r-1)!}

\binom{n+1}{r}=\frac{(n+1)!}{(n+1 -r)! r!}

\binom{n}{r}=\frac{n!}{(n-r)!r!} + \binom{n}{r-1}

= \frac{n!}{(n-r)!r!} + \frac{n!}{(n+1 -r)!(r-1)!} = \frac{n!(n+1 -r)!(r-1)!+ n!(n-r)!r! }{(n-r)!r!(n+1 -r)!(r-1)!}= \frac{n!\left [ (n+1 -r)!(r-1)! + (n-r)!r! \right ] }{(n-r)!r!(n+1 -r)!(r-1)!}

\frac{n!\left [ [(n+1 -r)(n-r)(n-r-1)....2.1](r-1)! + [(n-r)(n-r-1)....2.1]r! \right ] }{[(n-r)(n-r-1)....2.1]r!(n+1 -r)!(r-1)!} = \frac{n!\left [ (n+1 -r)(r-1)! +r! \right ] }{r!(n+1 -r)!(r-1)!}

= \frac{n!\left [ (n+1 -r)[(r-1)(r-2)(r-3)...2.1] + (r)(r-1)(r-2)(r-3)...2.1 \right ] }{(r)!(n+1 -r)![(r-1)(r-2)(r-3)...2.1]} = \frac{n!\left [ (n+1 -r) + r \right ] }{r!(n+1 -r)!}

\frac{n!(n+1)}{r!(n+1 -r)!} = \frac{(n+1)!}{r!(n+1 -r)!}

(1+x)^n = 1 +nx + .... + \binom{n}{r} x^r+ ....+ x^n

Suppose the results hold for a particular value of n, say k ;

(1+x)^k= 1 +kx + .... + \binom{k}{r} x^r+ ....+ x^k

Then adding the next term of the series

x^{(k+1)}

on both sides;

(1+x)^k + x^(k+1)= 1 +kx + .... + \binom{k}{r} x^r+ ....+ x^k + x^{(k+1)}

So I need to proof that

(1+x)^k + x^{(k+1)} = (1+x)^ {(k+1)}

this where i have a problem

Please can i have help as I am having problems with this one how do i use proof by induction to complete the 2nd part of the question

thank you

(edited 4 years ago)

Reply 2

DFranklin

Original post by bigmansouf

\binom{n}{r}=\frac{n!}{(n-r)!r!}

\binom{n}{r-1}=\frac{n!}{(n-(r-1))!(r-1)!} = \frac{n!}{(n+1 -r)!(r-1)!}

\binom{n+1}{r}=\frac{(n+1)!}{(n+1 -r)! r!}

\binom{n}{r}=\frac{n!}{(n-r)!r!} +\binom{n}{r-1}

The last of these is clearly incorrect. Put the first 3 all over the same denominator:

\binom{n}{r}=\frac{n!}{(n-r)!r!} = \frac{n!(n+1-r)}{(n+1-r)!r!}

\binom{n}{r-1}=\frac{n!}{(n-(r-1))!(r-1)!} = \frac{n!}{(n+1 -r)!(r-1)!} = \frac{n!r}{(n+1-r)!r!}

\binom{n+1}{r}=\frac{(n+1)!}{(n+1 -r)! r!}

Take out the common factor of

\frac{n!}{(n+1-r)!r!}

and your problem reduces to showing (n+1-r)+r = n + 1.

Suppose the results hold for a particular value of n, say k ;

(1+x)^k= 1 +kx + .... + \binom{k}{r} x^r+ ....+ x^k

Then adding the next term of the series

x^{(k+1)}

on both sides;

You should not be adding

x^{k+1}

to both sides, you should be multiplying both sides by (1+x). If you then calculate the coefficient of x^r on both sides, you should be able to show it's equal for r = 0, 1, ..., k+1 and so the two sides are identical.

(edited 4 years ago)

Reply 3

bigmansouf

Original post by DFranklin

The last of these is clearly incorrect. Put the first 3 all over the same denominator:

\binom{n}{r}=\frac{n!}{(n-r)!r!} = \frac{n!(n+1-r)}{(n+1-r)!r!}

\binom{n}{r-1}=\frac{n!}{(n-(r-1))!(r-1)!} = \frac{n!}{(n+1 -r)!(r-1)!} = \frac{n!r}{(n+1-r)!r!}

\binom{n+1}{r}=\frac{(n+1)!}{(n+1 -r)! r!}

Take out the common factor of

\frac{n!}{(n+1-r)!r!}

and your problem reduces to showing (n+1-r)+r = n + 1.

You should not be adding

x^{k+1}

Original post by bigmansouf

Question:
Show that

\binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r}

, and prove by induction that

(1+x)^n = 1 +nx + .... + \binom{n}{r} x^r+ ....+ x^n

where

\binom{n}{r} = \frac{n!}{(n-r)!r!}

and r is positive integer, less than or equal to n.

\binom{n}{r}=\frac{n!}{(n-r)!r!}

\binom{n}{r-1}=\frac{n!}{(n-(r-1))!(r-1)!} = \frac{n!}{(n+1 -r)!(r-1)!}

\binom{n+1}{r}=\frac{(n+1)!}{(n+1 -r)! r!}

\binom{n}{r}=\frac{n!}{(n-r)!r!} + \binom{n}{r-1}

= \frac{n!}{(n-r)!r!} + \frac{n!}{(n+1 -r)!(r-1)!} = \frac{n!(n+1 -r)!(r-1)!+ n!(n-r)!r! }{(n-r)!r!(n+1 -r)!(r-1)!}= \frac{n!\left [ (n+1 -r)!(r-1)! + (n-r)!r! \right ] }{(n-r)!r!(n+1 -r)!(r-1)!}

\frac{n!\left [ [(n+1 -r)(n-r)(n-r-1)....2.1](r-1)! + [(n-r)(n-r-1)....2.1]r! \right ] }{[(n-r)(n-r-1)....2.1]r!(n+1 -r)!(r-1)!} = \frac{n!\left [ (n+1 -r)(r-1)! +r! \right ] }{r!(n+1 -r)!(r-1)!}

= \frac{n!\left [ (n+1 -r)[(r-1)(r-2)(r-3)...2.1] + (r)(r-1)(r-2)(r-3)...2.1 \right ] }{(r)!(n+1 -r)![(r-1)(r-2)(r-3)...2.1]} = \frac{n!\left [ (n+1 -r) + r \right ] }{r!(n+1 -r)!}

\frac{n!(n+1)}{r!(n+1 -r)!} = \frac{(n+1)!}{r!(n+1 -r)!}

(1+x)^n = 1 +nx + .... + \binom{n}{r} x^r+ ....+ x^n

Suppose the results hold for a particular value of n, say k ;

(1+x)^k= 1 +kx + .... + \binom{k}{r} x^r+ ....+ x^k

Then adding the next term of the series

x^{(k+1)}

on both sides;

(1+x)^k + x^(k+1)= 1 +kx + .... + \binom{k}{r} x^r+ ....+ x^k + x^{(k+1)}

So I need to proof that

(1+x)^k + x^{(k+1)} = (1+x)^ {(k+1)}

this where i have a problem

Please can i have help as I am having problems with this one how do i use proof by induction to complete the 2nd part of the question

thank you

(1+x)^{k}(1+x) = \left (1 + kx + ...+ \binom{k}{r}x^r + ......+ x^k \right ) (1+x)[br][br](1+x)^{k+1} = \left ((1+x) 1 + (1+x)kx + ...+ (1+x) \binom{k}{r}x^r + ......+ (1+x)x^k \right )[br][br](1+x)^{k+1} = \left (1+x + ....+ kx + kx^2 ...+ \binom{k}{r}x^r + \binom{k}{r}x^{r+1} + ......+ x^k +x^{k+1} \right )

The problem is that i am finding difficulty summing this up

\left (1+x + ....+ kx + kx^2 ...+ \binom{k}{r}x^r + \binom{k}{r}x^{r+1} + ......+ x^k +x^{k+1} \right )

S_{n} = \frac{a(r^{n}-1)}{r-1} = \frac{1(x^{k+1}-1)}{x-1}= \frac{(x^{k+1}-1)}{x-1}

I think that the common ratio is probably not x or it could be kx- but I dont know.

This is what I have done so far. Please can i have some pointers

thank you

Reply 4

mqb2766

Write the (1+x)^n out in terms of the nCr terms, then multiply by (1+x) and collect the new coefficients for each x term. Each should be the sum of two nCr terms and you can use the first result you proved.

As an example
(1+x)^2 = 2C0 + 2C1*x + 2C2*x^2
(1+x)^2*(1+x) = 2C0 + (2C0+2C1)*x + (2C1+2C2)*x^2 + 2C2*x^3 = ....

Original post by bigmansouf

(1+x)^{k}(1+x) = \left (1 + kx + ...+ \binom{k}{r}x^r + ......+ x^k \right ) (1+x)[br][br](1+x)^{k+1} = \left ((1+x) 1 + (1+x)kx + ...+ (1+x) \binom{k}{r}x^r + ......+ (1+x)x^k \right )[br][br](1+x)^{k+1} = \left (1+x + ....+ kx + kx^2 ...+ \binom{k}{r}x^r + \binom{k}{r}x^{r+1} + ......+ x^k +x^{k+1} \right )

The problem is that i am finding difficulty summing this up

\left (1+x + ....+ kx + kx^2 ...+ \binom{k}{r}x^r + \binom{k}{r}x^{r+1} + ......+ x^k +x^{k+1} \right )

S_{n} = \frac{a(r^{n}-1)}{r-1} = \frac{1(x^{k+1}-1)}{x-1}= \frac{(x^{k+1}-1)}{x-1}

I think that the common ratio is probably not x or it could be kx- but I dont know.

This is what I have done so far. Please can i have some pointers

thank you

(edited 4 years ago)

Reply 5

username4750946

What level of maths is this? Is it A-level maths?

Reply 6

mqb2766

For edexcel, binomial (nCr) is A level maths and induction is further maths. The combination of the two topics is beyond what is normally asked. It is just Pascals triangle though ...
Im sure the OP will say where the question comes from.

Original post by Satyr

What level of maths is this? Is it A-level maths?

(edited 4 years ago)

Reply 7

ghostwalker

Original post by bigmansouf

(1+x)^{k+1} = \left ((1+x) 1 + (1+x)kx + ...+ (1+x) \binom{k}{r}x^r + ......+ (1+x)x^k \right )[br][br](1+x)^{k+1} = \left (1+x + ....+ kx + kx^2 ...+ \binom{k}{r}x^r + \binom{k}{r}x^{r+1} + ......+ x^k +x^{k+1} \right )

Original post by bigmansouf

The problem is that i am finding difficulty summing this up

\left (1+x + ....+ kx + kx^2 ...+ \binom{k}{r}x^r + \binom{k}{r}x^{r+1} + ......+ x^k +x^{k+1} \right )

S_{n} = \frac{a(r^{n}-1)}{r-1} = \frac{1(x^{k+1}-1)}{x-1}= \frac{(x^{k+1}-1)}{x-1}

I think that the common ratio is probably not x or it could be kx- but I dont know.

It really should be obvious that there is no common ratio, and this is not a geometric progression.

Keep in mind what you're trying to prove, and it should be clear that a summation across all the terms is not what's required.

Reply 8

bigmansouf

Original post by Satyr

What level of maths is this? Is it A-level maths?

it is an A level extension question that is designed to test knowledge and understanding

Reply 9

bigmansouf

Original post by ghostwalker

Not checked the working.

But, you've only got one term for each power of x there.

And that's because, IMO, you've only used one "middle term", the x^r. So, your expansion is rather misleading, and isn't going to facilitate regrouping of terms - which is clearly what the first part of the question is relating to.

It really should be obvious that there is no common ratio, and this is not a geometric progression.

Keep in mind what you're trying to prove, and it should be clear that a summation across all the terms is not what's required.