Tomer, there are a number of problems with this. The surest sign of that is that you give a definition for [sub]n[/sub]C[sub]k[/sub], but then you never appear to actually use it anywhere. If you're trying to prove that [sub]n[/sub]C[sub]k[/sub] is equal to something, don't you think you would have to actually use the definition of [sub]n[/sub]C[sub]k[/sub]?


[QUOTE=blob100;219795]Proof by induction (binomial theorem):
We see define [SUB]n[/SUB]C[SUB]k[/SUB] as the number of combinations of k units taken from a set of n units.[/QUOTE]

This is *not* the Binomial Theorem. Remember I told you to look that up? This is merely a proof that the formula for binomial coefficients matches our notion of "combinations of n things taken k at a time".

Also, I've no idea what you mean by "units" in this context.

[QUOTE=blob100;219795]Proposition:
[SUB]n[/SUB]C[SUB]k[/SUB]=(n!)/(P!k!)
P=n-k.

We will do so by induction on n.
Step 1:
Showing [SUB]0[/SUB]C[SUB]k[/SUB] agree the terms (for n=0, the proposition is true).
[SUB]0[/SUB]C[SUB]k[/SUB]=1.
(0!)/(P!k!)=1.
[/QUOTE]

Given your definition for [sub]n[/sub]C[sub]k[/sub], what does [sub]0[/sub]C[sub]k[/sub] mean? How do we take k "units" from a set of 0 "units"?
And when n = 0, then what is P? Shouldn't it be 0-k = -k? What is (-k)! ?


[QUOTE=blob100;219795]
Step 2:
Assuming that the formula is true for a given n and all 0≤ k≤n.

Step 3:
Showing that for n+1 the proposition is true if it is for n.
We assumed:
[SUB]n[/SUB]C[SUB]k[/SUB]=(n!)/(P!k!),
And we try to prove:
[SUB]n+1[/SUB]C[SUB]k[/SUB]=((n+1)!)/(P!k!).
[/QUOTE]

No, that last line isn't correct. You need (n+1-k)! in the denominator, but you have P!, which by your definition is (n-k)!
This is a good example of adding an extra variable that doesn't do much for you except confuse you. You did define it, but you'd be better off if you simply hadn't introduced it at all.

[QUOTE=blob100;219795]
We see: k=0, ((n+1)!)/((n+1)!0!)=1.
And: k=n+1, ((n+1)!)/(0!(n+1)!)=1
[/QUOTE]

Um, okay, yes we see that. But so what? You don't actually show that these correspond in any way to the definition of [sub]n+1[/sub]C[sub]0[/sub] or [sub]n+1[/sub]C[sub]n+1[/sub].

[QUOTE=blob100;219795]
And for 0≤ k≤n, [SUB]n[/SUB]C[SUB]k[/SUB]+[SUB]n[/SUB]C[SUB]k-1[/SUB].
[/QUOTE]

What [I]about[/I] [SUB]n[/SUB]C[SUB]k[/SUB]+[SUB]n[/SUB]C[SUB]k-1[/SUB]? Are you trying to say it's equal to something? What? This is like a sentence without a verb.


[QUOTE=blob100;219795]
So, we try porving [SUB]n[/SUB]C[SUB]k[/SUB]+[SUB]n[/SUB]C[SUB]k-1[/SUB] is equivallent to (n+1)!/((n+1-k)!k!).
[/QUOTE]

Why? You haven't shown that proving this is in any way related to the problem here.

[QUOTE=blob100;219795]
n!/(n-k)!k!+n!/(n-k+1)!(k-1)!=n!(n-k+1)/(n-k+1)!k!+n!k/(n-k+1)!k!=
n!(n+1)/(n-k+1)!k!.
Now, we would easily propose the next equation:
n!(n+1)/(n-k+1)!k!=(n+1)!/((n+1-k)!k!),
[/QUOTE]

Okay, you managed to add the two fractions correctly. But again, how is that related to the problem?

[QUOTE=blob100;219795]Which is what we tried to prove.[/QUOTE]

Why?

[QUOTE=blob100;219798]I think Discrete mathematics is as Euclidean Geometry a good course to learn proofs.
Do you agree with me?[/QUOTE]

Probably not. Most courses in discrete mathematics would probably assume that you already know how to do rigorous proofs. Though I would need to know more about what you mean when you say discrete mathematics to know for sure. I.e. what specific material do you mean when you say discrete mathematics?

[quote=jyb;219800]Probably not. Most courses in discrete mathematics would probably assume that you already know how to do rigorous proofs. Though I would need to know more about what you mean when you say discrete mathematics to know for sure. I.e. what specific material do you mean when you say discrete mathematics?[/quote]
Induction, Recurtion, Graph theory, Set theory, Combinatorics, etc.

OK, you are on the right track.
However, I'll be pedantically "picky" because rigor and completeness are fundamental properties of a [B]formal proof[/B]. If you are just trying to convey "the concept of the proof", you can be a bit more lax, but, eventually, the formalism is expected when you claim to present a proof. But, even for "conceptual proofs", the permitted laxness is related to making assertions without providing their proof. You must still make sure that the statements are accurate and that they are not open to unintended interpretation.

[QUOTE=blob100;219795]Proof by induction (binomial theorem):
We see define [sub]n[/sub]C[sub]k[/sub] as the number of combinations of k units taken from a set of n units.

Proposition:
[sub]n[/sub]C[sub]k[/sub]=(n!)/(P!k!)
where P=n-k.

And we try to prove:
[sub]n+1[/sub]C[sub]k[/sub]=((n+1)!)/(P!k!).[/QUOTE]

No, [sub]n+1[/sub]C[sub]k[/sub]=((n+1)!)/((n-k+1)!k!).
You have written ... =((n+1)!)/((n-k)!k!)

[QUOTE]And for 0 ≤ k ≤ n, [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub].[/QUOTE]

What does this mean? It is a clause, not an equation.
Further, you give not justification for choosing these terms.

[QUOTE]Which is what we tried to prove.[/QUOTE]
(The customary nomenclature is "QED".)

[quote=jyb;219799]Tomer, there are a number of problems with this. The surest sign of that is that you give a definition for [sub]n[/sub]C[sub]k[/sub], but then you never appear to actually use it anywhere. If you're trying to prove that [sub]n[/sub]C[sub]k[/sub] is equal to something, don't you think you would have to actually use the definition of [sub]n[/sub]C[sub]k[/sub]?



Also, I've no idea what you mean by "units" in this context.

Um, okay, yes we see that. But so what? You don't actually show that these correspond in any way to the definition of [sub]n+1[/sub]C[sub]0[/sub] or [sub]n+1[/sub]C[sub]n+1[/sub]

What [I]about[/I] [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub]? Are you trying to say it's equal to something? What? This is like a sentence without a verb.

Why? You haven't shown that proving this is in any way related to the problem here.

Okay, you managed to add the two fractions correctly. But again, how is that related to the problem?
[/quote]

[sub]n[/sub]C[sub]k[/sub] is a symbol discussed before, it means:
The number combinations of sub-sets of k objects taken from n objects (a set of n objects).
Moreover, by unit I meant object (my English isn't pretty good, as you assumed).

"Um, okay, yes we see that. But so what? You don't actually show that these correspond in any way to the definition of [sub]n+1[/sub]C[sub]0[/sub] or [sub]n+1[/sub]C[sub]n+1[/sub]."

"What [I]about[/I] nCk+nCk-1? Are you trying to say it's equal to something? What? This is like a sentence without a verb."

This was corresponding the values of k which are 0,n+1 and the naturals in the interval [0,n+1].
I wanted to show what the value of [sub]n[/sub]C[sub]k[/sub] is for every value of k.
Starting with showing that for k=0,n+1 the formula is true, and then putting the proof for the formula for every 0<k<n+1.
We would say this if 0<k<n+1 the number of combinations is [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub].
By pascal's rule we would say that [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] equls (n+1)!/k!(n-k+1)!.
The result (the equation) shows that for 0<k<n+1, the number of combinations is (n+1)!/k!(n-k+1)!.

[QUOTE=blob100;219805]By pascal's rule we would say that [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] equals (n+1)!/k!(n-k+1)![/QUOTE]

Some problems here:

First, Pascal's rule is:
[sub]n+1[/sub]C[sub]k[/sub] = [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub]

Note that this is an equation, not just some terms dangling in space.
And the rule does not express the value in direct terms of n and k.

Now, if you wish to use this in your proof, first you should state an argument for its applicability.

Then the validity is established in an algebraic step by substituting the formula definitions for each of the terms and showing that both sides of the equation reduce to the same thing.

[QUOTE=Wacky;219811]Some problems here:

First, Pascal's rule is:
[sub]n+1[/sub]C[sub]k[/sub] = [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub]

Note that this is an equation, not just some terms dangling in space.
And the rule does not express the value in direct terms of n and k.

Now, if you wish to use this in your proof, first you should state an argument for its applicability.

Then the validity is established in an algebraic step by substituting the formula definitions for each of the terms and showing that both sides of the equation reduce to the same thing.[/QUOTE]

Allow me to suggest that for proving n_C_k is the number of sets of
k items taken from n items that a direct proof by counting is usually
easier.

One starts by proving that the number of rearrangements of a set of
size k equals k!. This can be done directly by counting them.

[QUOTE=R.D. Silverman;219815]Allow me to suggest that for proving n_C_k is the number of sets of
k items taken from n items that a direct proof by counting is usually
easier.
[/QUOTE]

Tomer isn't trying to prove that [sub]n[/sub]C[sub]k[/sub] is the number of sets of k items taken from n items. He [I]defined[/I] [sub]n[/sub]C[sub]k[/sub] that way. He's trying to prove that [sub]n[/sub]C[sub]k[/sub] = n!/((n-k)!k!).

Of course it doesn't much matter which way he does it. The important thing is to prove the number of combinations is equal to the fraction, regardless of which way he chooses to define [sub]n[/sub]C[sub]k[/sub]. But for purposes of reading his proof, it's very important to know which way he defined it, so we know what he thinks he's trying to prove.

And in his case, he never makes any reference whatsoever to his definition after he makes it, so the proof can't possibly be valid.

[QUOTE=blob100;219805][sub]n[/sub]C[sub]k[/sub] is a symbol discussed before, it means:
The number combinations of sub-sets of k objects taken from n objects (a set of n objects).
Moreover, by unit I meant object (my English isn't pretty good, as you assumed).

"Um, okay, yes we see that. But so what? You don't actually show that these correspond in any way to the definition of [sub]n+1[/sub]C[sub]0[/sub] or [sub]n+1[/sub]C[sub]n+1[/sub]."

"What [I]about[/I] nCk+nCk-1? Are you trying to say it's equal to something? What? This is like a sentence without a verb."

This was corresponding the values of k which are 0,n+1 and the naturals in the interval [0,n+1].
I wanted to show what the value of [sub]n[/sub]C[sub]k[/sub] is for every value of k.
Starting with showing that for k=0,n+1 the formula is true, and then putting the proof for the formula for every 0<k<n+1.[/QUOTE]

But you [I]don't[/I] show that it's true. You simply assert that it's true. You say that ((n+1)!)/((n+1)!0!)=1, but you don't show that this is equal to [sub]n[/sub]C[sub]0[/sub], given your definition of [sub]n[/sub]C[sub]k[/sub].

[QUOTE=blob100;219805]We would say this if 0<k<n+1 the number of combinations is [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub].
By pascal's rule we would say that [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] equls (n+1)!/k!(n-k+1)!.
The result (the equation) shows that for 0<k<n+1, the number of combinations is (n+1)!/k!(n-k+1)!.[/QUOTE]

Again, you make no reference to the definition of [sub]n[/sub]C[sub]k[/sub], so how does this show anything about [sub]n+1[/sub]C[sub]k[/sub]?

[QUOTE=R.D. Silverman;219815]One starts by proving that the number of rearrangements of a set of size k equals k![/QUOTE]

Bob,

I, too, would have approached this from the [SUB]n[/SUB]P[SUB]n[/SUB] -> [SUB]n[/SUB]P[SUB]k[/SUB] -> [SUB]n[/SUB]C[SUB]k[/SUB] path.

However, Tomer chose another path and the proof can be accomplished that way also, and without too much difficulty.

To me, the important thing is that he display all of the elements of the proof.
I didn't discourage him because he may be more comfortable with his chosen path.

Using his approach, he needs to show that Pascal's rule applies and that, by algebra, n!/((k!(n-k)!) is consistent with this rule and the boundary conditions.

Richard

[QUOTE=Wacky;219819]Bob,

I, too, would have approached this from the [SUB]n[/SUB]P[SUB]n[/SUB] -> [SUB]n[/SUB]P[SUB]k[/SUB] -> [SUB]n[/SUB]C[SUB]k[/SUB] path.

However, Tomer chose another path and the proof can be accomplished that way also, and without too much difficulty.

To me, the important thing is that he display all of the elements of the proof.
I didn't discourage him because he may be more comfortable with his chosen path.

Using his approach, he needs to show that Pascal's rule applies and that, by algebra, n!/((k!(n-k)!) is consistent with this rule and the boundary conditions.

Richard[/QUOTE]


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.