reenmachine said:
When you say that you make it clearer what the variables represent , do you mean both ##n## and ##k## being arbitrary elements of N with ##k## being equal or smaller than ##n##?
Yes.
reenmachine said:
Do you mean that by only using the binomial coefficients in the beginning of the second part of my proof , it remained unclear what ##k## and ##n## really are?
If your readers understand binomial coefficients and trust that you do too, then they will assume that n and k are natural numbers such that k≤n. But you should still say that explicitly. You also need to make it clear if n and k are arbitrary or if they have been assigned some specific values, like n=7, k=2. I suppose that we could use the convention that every time we don't assign values like this, and don't use the words "there exists", our statements should be interpreted as "for all" statements. But you would have to
say that somewhere. I don't recommend this approach, since it doesn't save a lot of time or space, and makes the proofs a bit harder to follow.
reenmachine said:
About not stating ##\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}## as a "for all" statement , do you mean that it doesn't rigorously implied that this is true for all ##n,k \in N## , so basically it looks like I was using the formula with none-arbitrary variables (or at least that I didn't eliminate the possibility that this was the case)?
Yes, you didn't eliminate that possibility.
reenmachine said:
Now assume ##\binom{n}{k} \in\mathbb N## for all ##k##.
Here you left n undeclared. A simple "let ##n\in\mathbb N## be arbitrary" would have taken care of that. "For all k" is also a bit careless, since you don't mean that k can be equal to ##\pi-i##. We don't have to worry about ##\pi## and ##i## if we say that everywhere in this proof, the scope of our "for all" and "there exists" is ##\mathbb N##. But then we still have a problem with ##k## such that ##k>n##.
reenmachine said:
This implies that ##\binom{n}{k-1} \in\mathbb N## for all ##k>0##.
Same problems here.
reenmachine said:
Since ##\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}##
Here you say nothing about n or k.
reenmachine said:
, we know that ##\binom{n+1}{k} \in\mathbb N## for all ##k>0##
A statement that involves an undeclared k implies a statement "for all k>0"?
reenmachine said:
Sorry but I'm not sure in which context you're saying we should prove this identity so I'm not sure if I'm following you...
The book defined n! as the number of non-repeating lists with n entries, and ##\binom n k## as the number of subsets that can be made by choosing k elements from any set with n elements. I don't like these definitions. How are we supposed to use them in proofs? Consider e.g. the proof that
$$\binom{n+1}{k}=\binom n k+\binom{n}{k-1}$$ for all natural numbers n and k such that k≤n. When I read the proof discussed earlier, I pictured two boxes, the first one containing n+1 balls numbered from 0 to n, and the second one empty. Then I thought about how many ways there are to move k balls from the first box to the second. The total number must be equal to the number of ways to move k balls, none of which is numbered 0, plus the number of ways to move the one numbered 0 and k-1 more balls. Presumably, you had a similar image in your head. So are we really using the definition, or just a visual representation of our understanding of it?
I would say that it's the latter. The book's definition of ##\binom n k## means that ##\binom n k## is the cardinality of the set of all subsets of ##n=\{0,\dots,n-1\}## with cardinality ##k##. To prove that some set X has cardinality 3 for example, we would have to prove that there's a bijection from X into {0,1,2}. But we're not doing this sort of thing at all. We're just imagining some numbered balls being moved around.
So is the proof rigorous? Is it acceptable at all? These aren't easy questions. I think the answer is that proofs like this one are significantly less rigorous than the other proofs we've been doing, but are still (just barely) OK. The reason why they're OK is that the only proofs that are 100% rigorous are the ones where all the statements are written in the formal language of set theory, and it's perfectly clear in every step which axioms of our proof theory that we're using. (A proof theory is a definition of what we mean by a "proof"). The proofs we've been doing are at the level of rigor where the goal is to come up with an argument that would convince an experienced mathematician that a formal proof exists.
A mathematician with experience working with these "visual representations" of the underlying concepts will probably find the argument convincing. That's why I can't dismiss it outright. But I'm still more comfortable with definitions and proofs where we work directly with the mathematical concepts instead of some visual representations of them.
The simplest interpretation of the book's definition of n! is that n! is the cardinality of the set of injective functions from n to n, where n is defined by n={0,...,n-1}. But the book doesn't talk about cardinalities of sets of injective functions. Instead it conjures up images of things in the real world, such as numbered balls in a box, or lists written on paper. So the book's definition of n! has the same problems as its definition of ##\binom n k##.
These are the definitions I would prefer to use:
Define ##0!## by ##0!=1##. For all ##n\in\mathbb Z^+##, define ##n!## by ##n!=n(n-1)!##. For all ##n,k\in\mathbb N## such that ##k\leq n##, define
$$\binom n k =\frac{n!}{k!(n-k)!}.$$ These are simple definitions that are easy enough to use in proofs.
If we take these definitions as our starting point, a proof of ##\binom{n+1}{k}=\binom n k+\binom{n}{k-1}## that actually uses them will be much more convincing than an argument that relies on visual representations of the binomial coefficients.
