Mathematical induction with factorials problem

[Matherios]

Hello, i would really appreciate if somebody could help with this problem for n=>1
My first step was to prove for n=1 which is true.
Then i use the inductive hypothesis where n=k for k=>1.
After i try to do the inductive step where i end up (k+1+1)!/(k+1+1-2)!*2! = (K+1+2)!/ (K+1+2-3)!*3! which is not equal at all.
Please help and show me where im wrong.

 

[Romsek]

assume true for \(\displaystyle n\)
[MATH] \sum \limits_{k=1}^{n+1} \dbinom{k+1}{2} = \\ \sum \limits_{k=1}^n \dbinom{k+1}{2} + \dbinom{n+2}{2} =\\ \dbinom{n+2}{3} + \dbinom{n+2}{2} [/MATH]
Forget about all the factorials for a sec and look at the form of the last expression.
From the structure of Pascal's triangle

[MATH]\dbinom{n+2}{3}+\dbinom{n+2}{2} = \dbinom{n+3}{3} =\dbinom{(n+1)+2}{3}[/MATH]
So the assertion is true for [MATH](n+1)[/MATH] given that it's true for [MATH]n[/MATH].
You showed it's true for [MATH]n=1[/MATH] thus it's true for all [MATH]n\geq 1[/MATH]

 

[Matherios]

Can it be done with another way instead of the pascal triangle?
Cause we never were taught Pascal's triangle.
Thanks for the fast answer aswell!!

 

[MarkFL]

When working mathematical induction problems involving binomial coefficients, it often becomes very useful to know (or at least be aware of) Pascal's Rule:

[MATH]{n-1 \choose k}+{n-1 \choose k-1}={n \choose k}[/MATH]

Pascal's rule - Wikipedia

en.wikipedia.org

 

[Romsek]

Can it be done with another way instead of the pascal triangle?
Cause we never were taught Pascal's triangle.
Thanks for the fast answer aswell!!

I can't see being taught combinatorics without at least a passing reference to Pascal's triangle....

Let's just see if we can prove the general version MarkFL posted.

[MATH] \dbinom{n-1}{k} + \dbinom{n-1}{k-1} = \\ \dfrac{(n-1)!}{k!(n-1-k)!} + \dfrac{(n-1)!}{(k-1)!(n-k)!} = \\ \dfrac{(n-1)!}{(k-1)!(n-k-1)!} \cdot \left(\dfrac{1}{k} + \dfrac{1}{n-k}\right) = \\ \dfrac{(n-1)!}{(k-1)!(n-k-1)!} \cdot \dfrac{n}{k(n-k)} = \\ \dfrac{n!}{k!(n-k)!} = \dbinom{n}{k} [/MATH]

 

[Steven G]

I prefer a different proof from Romsek.

If you want to choose r objects from n objects you can do so as follows: You can find the number of ways to do this given that you pick the 1st object plus the number of ways if you do not pick the 1st object.
This gives us that _nC_k= _n-1C_k-1 + _n-1C_k

 

[Matherios]

Thanks for all the answers guys i really appreciate it!!

 

[Deleted member 4993]

Hello! I understand mathematical induction for the most part but I can't get a hang of proving inequalities.

Start a new thread.

Post problem explaining where you are stuck!