[QUOTE=R.D. Silverman;219850]The purely inductive proof is a bit more complicated, because for n_C_k,
there are TWO variables involved and you have to do more than one
induction.[/QUOTE]

Agreed. But it is not difficult to do that.
Further, while formulating such a proof, Tomer may recognize some other path that he will find even less difficult.

Remember that the goal is "to produce a rigorous proof", not "to produce a proof exclusively by induction".

I believe that Tomer is honestly trying to learn how to present a proper proof. We should encourage him to make progress and help by pointing out any weaknesses in his presentation.

Just as there are two "dimensions" to the inductive proof, there are two dimensions to Tomer's training. One of them is the establishment of logical steps in a proof and preparing a formal proof of each step. The other is to prove a particular formula. In my opinion, as long as he isn't going in a totally wrong direction with respect to the latter, we should welcome progress on the former even if that means that the journey meanders a bit.

[LEFT][FONT=Times New Roman][SIZE=3]We define n_C_k as the number of combinations of k objects taken from a set of n objects.[/SIZE][/FONT][/LEFT]

[LEFT][FONT=Times New Roman][SIZE=3]Proposition:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]n_C_k=n!/(n-k)!k!.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]To formulate this proof, we will use induction on n.[/SIZE][/FONT][/LEFT]

[LEFT][FONT=Times New Roman][SIZE=3]Step 1:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]We will start our proof by the first step, showing that for n=0 the equation is true.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]So, by locating 0 where n is written we have:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]0_C_k and 0!/(0-k)!k!.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]k must equal 0 because the maximal value of k out of n objects is 0,[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]This gives the next 0_C_0.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]And we assume easily 0_C_0=1.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]On the same time, by k=0, n!/(n-k)!k!=1/0!0!=1.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]This shows that for n=0 the proposition is true.[/SIZE][/FONT][/LEFT]

[LEFT][FONT=Times New Roman][SIZE=3]Step 2:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]To continue with the inductive proof, we will assume the proposition for every natural </=n and 0=/<k</=n.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]By proving that if we assume that last statement the proposition (the proposition the assumption corresponding to) is true for n+1, we complete the inductive proof.[/SIZE][/FONT][/LEFT]

[LEFT][FONT=Times New Roman][SIZE=3]Step 3:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]We prove that for n+1 the proposition is true if it is true for n.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]The next phrase is what we try to prove:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]n+1_C_k=(n+1)!/(n-k+1)!k! for any 0=/<k</=n+1,[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]n+1_C_k is of course concerning n+1 and (n+1)!/(n-k+1)!k! is what we see as the same phrase as n!/(n-k)!k! just for n+1.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]This means, proving the statement:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]The number of combinations between k objects out of n+ 1 object is similar to what we assumed equals it (by the proposition).[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]We will show that n+1_C_k is true for three kinds of values of k, [/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]We will show that for these three values, the proposition is true.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]The values of k are: k=0, k=n+1, 0<k<n+1,[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]And we easily assume that for proving that these all values of k show that the next n+1_C_k=(n+1)!/(n-k+1)!k! as a valid equation,[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]We proved the proposition.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]n+1_C_0 is of course 1, there is only one combination of 0 objects (0 itself),[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]And on the same time, (n+1)!/(n+1)!0! equals 1.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Corresponding to our goal, we see n+1_C_k=(n+1)!/(n-k)!k! for k=0.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]We see that both n+1_C_n+1 (k=n+1) and (n+1)!(n+1-n-1)!(n+1)! equal 1 (equivalent).[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]Now, we will continue to proving the statement for every 0<k<n+1.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]We try to prove that for these values of k (0<k<n+1) the value of n+1_C_k equals (n+1)!/(n-k+1)!k!.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]By pascal's rule we see the equation: n+1_C_k=n_C_k+n_C_k-1.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]This identify directs us to the next value of the right side of the equation:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]n_C_k (as we assumed on Step 2) equals n!/(n-k)!k!, and same with n_C_k-1 which equals (by the same assumption) n!/(n-k+1)!(k-1)!.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]This gives n+1_C_k equals to the sum of the two n!/(n-k+1)!(k-1)! and [/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]n!/(n-k)!k!.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]n!/(n-k)!k!+ n!/(n-k+1)!(k-1)!=(n+1)!/(n-k+1)!k! (by trivial conclusions of algebra).[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]This last statement directs us to n+1_C_k=(n+1)!/(n-k+1)!k! which is what we tried to prove till now.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3][/SIZE][/FONT]
[/LEFT]

[QUOTE=blob100;219890][LEFT][FONT=Times New Roman][SIZE=3]We define n_C_k as the number of combinations of k objects taken from a set of n objects.[/SIZE][/FONT][/LEFT]

[LEFT][FONT=Times New Roman][SIZE=3]Proposition:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]n_C_k=n!/(n-k)!k!.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]To formulate this proof, we will use induction on n.[/SIZE][/FONT][/LEFT]

[LEFT][FONT=Times New Roman][SIZE=3]Step 1:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]We will start our proof by the first step, showing that for n=0 the equation is true.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]So, by locating 0 where n is written we have:[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]0_C_k and 0!/(0-k)!k!.[/SIZE][/FONT]
[FONT=Times New Roman][SIZE=3]k must equal 0 because the maximal value of k out of n objects is 0,[/SIZE][/FONT]
[/QUOTE]

No.

For induction on n, you start by fixing a value of k. So you can take k = 1
and then k = 1 throughout the proof. The induction is on n. You start with
n=1.

Then you will need to fix n, and do an induction on k.

Then you will need to do a induction on both together.


And your last sentence is nonsense. You must start your proof by
counting the number of ways one can select 1 object from a set of size 1
and showing that this number is given by your formula.

Then you assume that the formula is true for arbitrary n (with k=1)
and must show that it is then true for n+1. This means showing that if
n_C_1 has the value given by the formula, then {n+1}_C_1 gives
the correct number of subsets of size 1 when n increases to n+1.
This means that you must independently COUNT the number of such subsets
and show that it satisfies the formula. So: if n_C_1 has some value,
say R, how do you count the number of subsets for {n+1} based
only upon n_C_1 = R? The number of such subsets will depend on R.
You must then show that this number satisfies your formula.

Then, you fix n to have some arbitrary large value and do induction
on k.

Then, you do an induction on n and k simultaneously.

[QUOTE=R.D. Silverman;219893]No.

For induction on n, you start by fixing a value of k. So you can take k = 1
and then k = 1 throughout the proof. The induction is on n. You start with
n=1.

Then you will need to fix n, and do an induction on k.

Then you will need to do a induction on both together.


And your last sentence is nonsense. You must start your proof by
counting the number of ways one can select 1 object from a set of size 1
and showing that this number is given by your formula.

Then you assume that the formula is true for arbitrary n (with k=1)
and must show that it is then true for n+1. This means showing that if
n_C_1 has the value given by the formula, then {n+1}_C_1 gives
the correct number of subsets of size 1 when n increases to n+1.
This means that you must independently COUNT the number of such subsets
and show that it satisfies the formula. So: if n_C_1 has some value,
say R, how do you count the number of subsets for {n+1} based
only upon n_C_1 = R? The number of such subsets will depend on R.
You must then show that this number satisfies your formula.

Then, you fix n to have some arbitrary large value and do induction
on k.

Then, you do an induction on n and k simultaneously.[/QUOTE]


Let me also add that at no time in the previous effort did you ever
actually COUNT the number of subsets and show that the formula
is correct. Furthermore, you are not allowed to use anything,
such as "pascal's rule' that has not already been proved.

I will present an example.

Suppose you know that for n = 50, that there are R subsets of size 17.
The induction *assumes* that the formula gives the correct answer.
You then let n = 51. You now need to determine 51_C_17 WITHOUT
USING THE FORMULA. (but you do use the value of R) You then need to
show that the value you get for n = 51 satifies the formula.

[quote=R.D. Silverman;219895]Let me also add that at no time in the previous effort did you ever
actually COUNT the number of subsets and show that the formula
is correct. Furthermore, you are not allowed to use anything,
such as "pascal's rule' that has not already been proved.

I will present an example.

Suppose you know that for n = 50, that there are R subsets of size 17.
The induction *assumes* that the formula gives the correct answer.
You then let n = 51. You now need to determine 51_C_17 WITHOUT
USING THE FORMULA. (but you do use the value of R) You then need to
show that the value you get for n = 51 satifies the formula.[/quote]

I can prove pascal's rule, furthermore, it is trivially true.

[QUOTE=blob100;219890]By Pascal's rule we see the equation: n+1_C_k=n_C_k+n_C_k-1.[[/QUOTE]

I have a problem with the way that you have used Pascal's rule. You have done so [B]without providing any justification[/B]. If you are going to use Pascal's rule, then you [B]must prove[/B] that it is applicable. Otherwise your argument is just a proof that x!/(x-y)!y! is a solution to the recursive definition f(x,y) = f(x-1,y)+f(x-1,y-1). You have not proven anything about the "number of combinations".

Don't get too caught up in Bob's "double induction" argument. It appears to me that your proof is headed toward a slightly different approach that does not rely upon induction on k.

[QUOTE=Wacky;219899]I have a problem with the way that you have used Pascal's rule. You have done so [B]without providing any justification[/B]. If you are going to use Pascal's rule, then you [B]must prove[/B] that it is applicable. Otherwise your argument is just a proof that x!/(x-y)!y! is a solution to the recursive definition f(x,y) = f(x-1,y)+f(x-1,y-1). You have not proven anything about the "number of combinations".

Don't get too caught up in Bob's "double induction" argument. It appears to me that your proof is headed toward a slightly different approach that does not rely upon induction on k.[/QUOTE]

I said earlier that the induction proof was cumbersome. I much
prefer a direct counting argument. It only takes a small number of
steps.

First of all, I can use pascal's rule,
Here is the proof:
We try to prove:
n_C_k=n-1_C_k-1+n-1_C_k.
The left side: the number of combinations we can make with k objects out of n objects.
Since 1</=[I]k</=[/I][I]n[/I] − 1, We can pick an arbitary J object of the set of the n objects ( the remaining sub-set is not empty).
For each k-set if J is chosen, there are n-1_C_k-1 ways to choose the remaining k-1 objects out of the remaining n-1 choices;
And there are n-1_C_k combinations with the remaining k objects out of the remaining n-1 objects (choices).
Finally we have n-1_C_k+n-1_C_k combinations of k objects with J included in each combination which is how n_C_k defined.

Is this a valid approach for the proof of the combinatorical theorem?:
[SUB]n[/SUB]C[SUB]k[/SUB]=[SUB]n[/SUB]C[SUB]k-1[/SUB](n-k/k).
This is of course a recursive phrase which can be written as:
[SUB]n[/SUB]C[SUB]k[/SUB]=(PI)[sup]J=k-1[/sup][sub]J=0[/sub](n-k+J)/(k-J),

We see these two statements:
(PI)[sup]J=k-1[/sup][sub]J=0[/sub](k-J)=k!
(PI)[sup]J=k-1[/sup][sub]J=0[/sub](n-k+J)=n!/(n-k)!
And by producting these two (the first proposition's right side) we get:
[SUB]n[/SUB]C[SUB]k[/SUB]=n!/(n-k)!k!.
*(PI)[sup]J=k-1[/sup][sub]J=0[/sub] is a product of the series with the index J=0 to J=k-1 (I didn't find how to write the index under and above the (PI)).

This approach is the proposition needed to be proved in the induction on k in the doubled-induction proof.

[QUOTE=blob100;219948]First of all, I can use pascal's rule[/QUOTE]
In presenting a proof, it is quite permissible to prove one theorem and thereafter use it in the proof of another theorem.

I'm sure that it is just a language issue, but "use" carries the connotation that the result of a theorem will be applied without proving the theorem itself at that point because it has already been established.

It is your intent to present and prove a theorem (Pascal's rule) so that you may use it in the subsequent proof. Therefore, a term such as "prove", "establish", or "verify", rather than the term "use", would describe better your intent.

[QUOTE]Here is the proof:
We try to prove:
n_C_k=n-1_C_k-1+n-1_C_k.
The left side: the number of combinations we can make with k objects out of n objects.
[/QUOTE]

Proving that a recursive formula describes some measure is essentially a proof by induction. Therefore, for completeness, you must also include the boundary conditions and show that the formulation applies in all instances.

So your method of proof is now:
Part 1: Prove that the "number of combinations" conforms to Pascal's rule (and each of the boundary conditions).

Part 2: Prove that [SUB]n[/SUB]C[SUB]k[/SUB] = n!/(k!(n-k)!) meets all of the conditions expressed in part 1.

For B a given non-empty set |B| will denote the large of the set (the number of objects in the set).
I have another approach to this proposition's proof (much easier):
We will first prove the next lemma:
For a given set A, |A|=n, and we define k as a natural number 0=/<k</=n.
The number of sequences which contain k objects out of A's objects is:
n(n-1)(n-2)....(n-k+1)=n!/(n-k)!.

Proof:
We see that for the first objects in the sequence we have n options to choose (there are n objects not contained in the sequence).
The next object is able to be n-1 options,
The next is n-2...
When we will choose the object number k (the last object in the sequence) will have n-k+1 options to choose.
This gives n(n-1)...(n-k+1)=n!/(n-k)!.

This last theorem gives the approach to prove our problem:
For the defined A,k,n we have:
n_C_k=n!/(n-k)!k!.
Where n_C_k is the number of combinations of k objects out of n objects.

We firstly see that the number of promotations of every sequence is k!
[SIZE=1]*I can prove this easily, but it does not seem to be nessecary.[/SIZE]

We would say that a combination is similar to a sub-set of A.
By this, we easily see that if there are k! promotations of every sequence, for every sub-set of A of k objects there are k! sequences of k objects.
(I mean, for every k! sequences of k objects there is [U]only one[/U] such sub-set of k objects).
So, if the theorem of the sequence counting was n!/(n-k)! the result of the sub-set counting will be n!(n-k)!k!.