Question about proof from a guy with a highschool education

[reenmachine]

woops , blunder

 

[1MileCrash]

n is assumed to be a nonnegative integer right off the bat because n! is only defined for those numbers.

Also, this proof comes into play with what we discussed earlier.

We already discussed why (n choose n) is 1.

And, you've shown already that (n choose k) = (n choose (n-k)) right? So what happens if k=0?

What you did proves it, I am just showing another way to look at it.

 

[reenmachine]

n is assumed to be a nonnegative integer right off the bat because n! is only defined for those numbers.

Also, this proof comes into play with what we discussed earlier.

We already discussed why (n choose n) is 1.

And, you've shown already that (n choose k) = (n choose (n-k)) right? So what happens if k=0?

I don't understand what you mean with your last sentence , I thought I already proved that if k=0 , then $\binom{n}{k}$ is an integer (1) in my post above.

I'm still trying to figure it all out , even if I fail in the end "playing" with all of this is making me understanding factorials more in depth so it can't be bad.

I'm trying to prove that $\binom{n+1}{k}$ always results in an integer from the assumption that $\binom{n}{k}$ always results as an integer.

Just trying to wrap my head around all of this and digest it to come up with a proof.I'm trying to deconstruct the entire formula using factorials but no success for the moment.I had two or three hints but all of them were wrong when I re-verified.

 

[micromass]

I don't understand what you mean with your last sentence , I thought I already proved that if k=0 , then $\binom{n}{k}$ is an integer (1) in my post above.

I'm still trying to figure it all out , even if I fail in the end "playing" with all of this is making me understanding factorials more in depth so it can't be bad.

I'm trying to prove that $\binom{n+1}{k}$ always results in an integer from the assumption that $\binom{n}{k}$ always results as an integer.

Just trying to wrap my head around all of this and digest it to come up with a proof.

The crucial part is that we assume that $\binom{n}{k}$ is an integer for all $k$. This is what we take as induction hypothesis. In particular, we see that $\binom{n}{k-1}$ is an integer for $k>0$.

 

[reenmachine]

The crucial part is that we assume that $\binom{n}{k}$ is an integer for all $k$. This is what we take as induction hypothesis. In particular, we see that $\binom{n}{k-1}$ is an integer for $k>0$.

Hmmm , so if $\binom{n}{k}$ is an integer for all $k$ , then $\binom{n}{k-1}$ is an integer for $k>0$ (even if K=0 , the final answer is 0 no? so that's still an integer (correct me if I'm wrong here)) , so basically the addition of two integers will always result in an integer , so since $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ , then $\binom{n+1}{k}$ is an integer...

 

[micromass]

Hmmm , so if $\binom{n}{k}$ is an integer for all $k$ , then $\binom{n}{k-1}$ is an integer for $k>0$ (even if K=0 , the final answer is 0 no? so that's still an integer (correct me if I'm wrong here)) , so basically the addition of two integers will always result in an integer , so since $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ , then $\binom{n+1}{k}$ is an integer...

Right, but you need a separate argument for $\binom{n+1}{0}$.

 

[reenmachine]

Right, but you need a separate argument for $\binom{n+1}{0}$.

Isn't it assumed from the proof of P(0)? Since $n$ is a dummy variable , what's the difference with n+1?

Let's try it anyway , assume k=0.We have $\binom{n+1}{0} = \frac{(n+1)!}{0!((n+1)-0)!} = \frac{(n+1)!}{1 \cdot (n+1)!} = \frac{(n+1)!}{(n+1)!} = 1$.

thoughts?
thank you!

 

[micromass]

Isn't it assumed from the proof of P(0)? Since $n$ is a dummy variable , what's the difference with n+1?

Technically, P(0) only says that $\binom{0}{0}$ is an integer. It doesn't say anything about $\binom{n}{0}$. But you proved it anyway, so that's fine then.

 

[reenmachine]

Another question , when you're facing a situation where you need to assume an argument such as Integer + Integer = Integer , do you have to prove it? This is what happened in the second part of the proof.

 

[1MileCrash]

I don't understand what you mean with your last sentence , I thought I already proved that if k=0 , then $\binom{n}{k}$ is an integer (1) in my post above.

You did, I was just showing you another way, that the things you've already proven can be applied to show that $\binom{n}{0}=\binom{n}{n-0}=1$.

A lot of times in proof classes, when writing a proof we simplify it greatly by referencing some other theorem that we proved in the class already. It's not necessary here by any means, it's just another way.

 

[micromass]

Another question , when you're facing a situation where you need to assume an argument such as Integer + Integer = Integer , do you have to prove it? This is what happened in the second part of the proof.

You can prove it if you want to. But in situations here, you can assume it's true.

 

[reenmachine]

Technically, P(0) only says that $\binom{0}{0}$ is an integer. It doesn't say anything about $\binom{n}{0}$. But you proved it anyway, so that's fine then.

Hmm , but I thought that the first part of the proof was that $\binom{n}{k}$ results in an integer if k=0.I thought the notation $n$ was any $x \in \mathbb{N}$?

thank you micromass!

 

[micromass]

Hmm , but I thought that the first part of the proof was that $\binom{n}{k}$ results in an integer if k=0.I thought the notation $n$ was any $x \in \mathbb{N}$?

thank you micromass!

The induction is on $n$, not on $k$. So $P(0)$ says that $\binom{0}{k}$ is an integer for all $k$.

 

[reenmachine]

The induction is on $n$, not on $k$. So $P(0)$ says that $\binom{0}{k}$ is an integer for all $k$.

LOL , well , this went over my head.

Because when I proved the first step , I only used 0 for k and ignored the value of n , so basically it worked for all n based on the computation of the factorials fractions (resulting in 1).

 

[Fredrik]

What you want to prove is this, right?

For all $n,k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

(I'm including 0 in $\mathbb N$). For each $n\in\mathbb N$, let $P(n)$ be the following statement:

For all $k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

You want to prove all of the infinitely many statements P(0),P(1),P(2),... The way to to do that is to prove the following two statements.
\begin{align}&P(0)\\ &\forall n\in\mathbb N~~ P(n)\Rightarrow P(n+1).\end{align} P(0) is the statement

For all $k\in\mathbb N$ such that $k\leq 0$, we have $\binom 0 k\in\mathbb N$.​

So to prove it, the natural way to start is "Let k be an arbitrary element of $\mathbb N$ such that k≤0". This statement assigns the value 0 to k. So you can continue like this
$$\binom 0 k =\binom 0 0 =\cdots$$
(This is not the easiest example of a proof by induction, since there's a second integer variable k that makes it harder to see how to define P(n)).

 

[Seydlitz]

I realize you're asking for the same problem as I do. It's already resolved. See this thread if you're interested. https://www.physicsforums.com/showthread.php?p=4451388&posted=1#post4451388

 

[reenmachine]

What you want to prove is this, right?

For all $n,k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

(I'm including 0 in $\mathbb N$). For each $n\in\mathbb N$, let $P(n)$ be the following statement:

For all $k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

You want to prove all of the infinitely many statements P(0),P(1),P(2),... The way to to do that is to prove the following two statements.
\begin{align}&P(0)\\ &\forall n\in\mathbb N~~ P(n)\Rightarrow P(n+1).\end{align} P(0) is the statement

For all $k\in\mathbb N$ such that $k\leq 0$, we have $\binom 0 k\in\mathbb N$.​

So to prove it, the natural way to start is "Let k be an arbitrary element of $\mathbb N$ such that k≤0". This statement assigns the value 0 to k. So you can continue like this
$$\binom 0 k =\binom 0 0 =\cdots$$
(This is not the easiest example of a proof by induction, since there's a second integer variable k that makes it harder to see how to define P(n)).

Hmm I thought I already proved it (more or less) in post 724 , 730 and 732.

Let me try it more officially.

------------------------------------------------------------------------------------------

We will attempt to prove that:

$\forall n,k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

$\forall n\in\mathbb N$, let $P(n)$ be the following statement:

For all $k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

We will first attempt to prove $P(0)$.Let $k$ be an arbitrary element of $\mathbb N$ such that $k≤0$.This gives us $\binom{0}{0} = \frac{0!}{0!(0-0)!} = \frac{1}{1 \cdot 1} = \frac{1}{1} = 1$.Since $1\in\mathbb N$ ,this proves $P(0)$.

Now assume $\binom{n}{k} \in\mathbb N$ for all $k$.This implies that $\binom{n}{k-1} \in\mathbb N$ for all $k>0$.Since $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ , we know that $\binom{n+1}{k} \in\mathbb N$ for all $k>0$ because it's the sum of two elements of $\mathbb N$ (which we assume as true).We're now left with $\binom{n+1}{0}$.This equals to $\frac{(n+1)!}{0!((n+1-0)!} = \frac{(n+1)!}{1 \cdot (n+1)!} = \frac{(n+1)!}{(n+1)!} = 1$.Since $1 \in\mathbb N$ , this proves that $P(n) \rightarrow P(n+1)$.

These previous proofs prove that $\forall n,k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.

-----------------------------------------------------------------------------------------

thoughts about this more official version of my proof attempt?

thank you!

 

[reenmachine]

I realize you're asking for the same problem as I do. It's already resolved. See this thread if you're interested. https://www.physicsforums.com/showthread.php?p=4451388&posted=1#post4451388

Hi , thanks for the info but I prefer trying to solve it myself before seeing other solutions

 

[Fredrik]

Hmm I thought I already proved it (more or less) in post 724 , 730 and 732.

Maybe you did. I didn't look closely at those posts. I just saw the "over my head" comment and assumed that the problem wasn't solved.

We will attempt to prove that:

$\forall n,k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

$\forall n\in\mathbb N$, let $P(n)$ be the following statement:

For all $k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

We will first attempt to prove $P(0)$.Let $k$ be an arbitrary element of $\mathbb N$ such that $k≤0$.This gives us $\binom{0}{0} = \frac{0!}{0!(0-0)!} = \frac{1}{1 \cdot 1} = \frac{1}{1} = 1$.Since $1\in\mathbb N$ ,this proves $P(0)$.

Now assume $\binom{n}{k} \in\mathbb N$ for all $k$.This implies that $\binom{n}{k-1} \in\mathbb N$ for all $k>0$.Since $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$ , we know that $\binom{n+1}{k} \in\mathbb N$ for all $k>0$ because it's the sum of two elements of $\mathbb N$ (which we choose to assume as true).We're now left with $\binom{n+1}{0}$.This equals to $\frac{(n+1)!}{0!((n+1-0)!} = \frac{(n+1)!}{1 \cdot (n+1)!} = \frac{(n+1)!}{(n+1)!} = 1$.Since $1 \in\mathbb N$ , this proves that $P(n) \rightarrow P(n+1)$.

These previous proofs prove that $\forall n,k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.

-----------------------------------------------------------------------------------------

thoughts about this more official version of my proof attempt?

Looks good. Here's how I would do the $P(n)\Rightarrow P(n+1)$ step:

Let $n\in\mathbb N$ be arbitrary. Suppose that $P(n)$ holds. Let $k$ be an arbitrary element of $\mathbb N$ such that $k\leq n$. If $k=0$, we have
$$\binom{n+1}{k} =\frac{(n+1)!}{0!(n+1-0)!} =1\in\mathbb N.$$ If $k>0$, we have
$$\binom{n+1}{k} =\binom n k + \binom{n}{k-1}\in\mathbb N.$$ (It follows immediately from $P(n)$ that both terms on the right are in $\mathbb N$). So for all $k\in\mathbb N$ such that $k\leq n$, we have $\binom{n+1}{k}\in\mathbb N$. This means that $P(n+1)$ holds.

The only part of this that's a significant improvement over your version is the first line, which make it clear what the variables represent. I don't think that's perfectly clear in your version. For example, you say that $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$, without making it a "for all" statement.

Note by the way that if we use my definition of n!, we have to use it to prove the identity $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$.

 

[reenmachine]

Maybe you did. I didn't look closely at those posts. I just saw the "over my head" comment and assumed that the problem wasn't solved.

Either way I don't think I'm strong enough yet in the "presentation" of my proofs to cut corners so it's a good idea to try my luck at some proofs once in a while

Looks good. Here's how I would do the $P(n)\Rightarrow P(n+1)$ step:

Let $n\in\mathbb N$ be arbitrary. Suppose that $P(n)$ holds. Let $k$ be an arbitrary element of $\mathbb N$ such that $k\leq n$. If $k=0$, we have
$$\binom{n+1}{k} =\frac{(n+1)!}{0!(n+1-0)!} =1\in\mathbb N.$$ If $k>0$, we have
$$\binom{n+1}{k} =\binom n k + \binom{n}{k-1}\in\mathbb N.$$ (It follows immediately from $P(n)$ that both terms on the right are in $\mathbb N$). So for all $k\in\mathbb N$ such that $k\leq n$, we have $\binom{n+1}{k}\in\mathbb N$. This means that $P(n+1)$ holds.

The only part of this that's a significant improvement over your version is the first line, which make it clear what the variables represent. I don't think that's perfectly clear in your version. For example, you say that $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$, without making it a "for all" statement.

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$? 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?

(take note that I do find your proof clearer myself , just wish to put my finger on why)

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)?

Note by the way that if we use my definition of n!, we have to use it to prove the identity $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$.

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...

thank you!

 

[Fredrik]

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.

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.

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.

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$.

This implies that $\binom{n}{k-1} \in\mathbb N$ for all $k>0$.

Same problems here.

Since $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$

Here you say nothing about n or k.

, 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"?

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.

 

[reenmachine]

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.

I will try to be more explicit when I introduce variables in different contexts in the future.Thank you!

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$.

This is one of those tough spot for me as far as what to leave assumed or what to explicitly say.I'm talking specifically about "for all k" being careless.

I stated I wanted to prove:

$\forall n,k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

Then defined P(N) with:

$\forall n\in\mathbb N$, let $P(n)$ be the following statement:

For all $k\in\mathbb N$ such that $k\leq n$, we have $\binom n k\in\mathbb N$.​

This is also without saying that the whole proof depends on factorials , are factorials assumed to be integers? Once I complete a proof it's getting easier to understand these details , but while in the process of trying to solve it , this is definitely another matter.Perhaps I should always wait a couple of hours at least before posting a proof?

A statement that involves an undeclared k implies a statement "for all k>0"?

LOL of course at this point I thought k was declared so it's not surprising that the rest of the proof doesn't make sense unless you assume what k is.

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.

Very insightful! So which level of rigor to use when doing a proof depends of what you are trying to achieve by proving , for exemple whether you really want to prove it completely or just demonstrate to a professionnal that's it's definitely provable (even rigorously) even if you didn't bother doing it in the first place.That being said , for a mathematician it's always better to write proof as rigorously as possible.

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.

See point above.

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$.

Hmm , seems like I am a bit rusty as far as functions goes.This isn't surprising since I only covered it at the end of the 10 pages long pdf that I used in the beginning of this adventure.I then realized the function's chapter was at the end of the book of proof so I just left these concepts aside until I reach this chapter.

(I have to edit here , I expressed myself badly on some definitions)

An injective function is when each elements of the domain is paired with his own element in the co-domain.A bijection is when each elements of the domain is paired with his own element of the co-domain and that the co-domain = range.Surjective means that all elements of the co-domain are paired with some element(s) of the domain.Is that correct?

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.

This definition clearly seems better than using the cardinality of the set of all subsets of $n=\{0,\dots,n-1\}$ with cardinality $k$.

thank you!

 

[CompuChip]

This is actually quite typical in mathematics, where you take an intuitive concept such as "the number of ways to order n objects", "the surface area of a square", "a straight line" or "parallel" and make a definition which at first sight is quite unrelated. Usually, it is shown at the point where the definition is made, that it corresponds to our intuition (for example in the case of n! you could show inductively that ordering n elements means putting the first one on one of n available spots and re-ordering the rest in one of the possible (n - 1)! ways) and then always proceed to work with the (often algebraic) definition (simply because, as you have seen, a definition like 0! = 1 and n! = n(n - 1)! is more convenient in calculations).

 

[reenmachine]

This is actually quite typical in mathematics, where you take an intuitive concept such as "the number of ways to order n objects", "the surface area of a square", "a straight line" or "parallel" and make a definition which at first sight is quite unrelated. Usually, it is shown at the point where the definition is made, that it corresponds to our intuition (for example in the case of n! you could show inductively that ordering n elements means putting the first one on one of n available spots and re-ordering the rest in one of the possible (n - 1)! ways) and then always proceed to work with the (often algebraic) definition (simply because, as you have seen, a definition like 0! = 1 and n! = n(n - 1)! is more convenient in calculations).

Thank you CompuChip!

 

[reenmachine]

They introduce this notation in the book of proof (page 78 section 3.4) :

Use the binomial theorem to show:
$\sum \binom{n}{k=0} 3^k \binom{n}{k}=4^n$

except that the first binomial coefficient isn't between parenthesis.

I'm not sure what they mean , beside the sum symbol there's the n , k=0 on top of each other without parenthesis.

I'm in need of some help on that one.

thank you!

 

[micromass]

They introduce this notation in the book of proof (page 78 section 3.4) :

Use the binomial theorem to show:
$\sum \binom{n}{k=0} 3^k \binom{n}{k}=4^n$

except that the first binomial coefficient isn't between parenthesis.

I'm not sure what they mean , beside the sum symbol there's the n , k=0 on top of each other without parenthesis.

I'm in need of some help on that one.

thank you!

They mean

$$\sum_{k=0}^n 3^k \binom{n}{k} = 4^n$$

So you sum from 0 to n.

 

[reenmachine]

Hey guys , I let this thread sleep a little bit as my reading of chapter 4 in the book of proof was going pretty well.I tried my luck at a couple of proofs and most of them went well but there's one that seems very simple yet I'm not sure how to prove it.

The theorem goes as follow:

If $x \in ℝ$ and $0>x>4$ , then $\frac{4}{x(4-x)}≥1$.

We know that $x+(4-x)=4$.This mean that the expression could be written as $\frac{4}{m \cdot n}$ with $m,n \in ℝ$ such that $m+n=4$.Basically , I wanted to prove that for all $y \in Z$ such that $\exists k \in Z$ such that $2k=y$ , the product of any combination of $a,b \in ℝ$ such that $a+b=y$ will always be the largest if both $a = \frac{y}{2}$ and $b = \frac{y}{2}$.

In clearer term , if you take any two elements of R that result(sum) in 4 and multiply them , you won't find a bigger one than 2 × 2= 4.Same if you take 6 as an exemple , the largest will be 3 × 3 = 9.If I proved that , it would prove the theorem since $\frac{4}{4} = 1$ and all others denominator would be smaller , resulting in a larger number than 1.

I'm lost on that one even though I have a strong feeling the answer isn't overly complicated.

thank you!

 

[reenmachine]

Wait , maybe something like $y+y=y+n+y-n$ , we check $(y)(y) = y^2$ versus $(y+n)(y-n)=y^2-n^2$? We have $y^2>y^2-n^2$ , could it prove my argument above?

 

[CompuChip]

If $x \in \mathbb{R}$ and $0>x>4$ , then $\frac{4}{x(4-x)}≥1$.

I'm sure that's not the theorem, because this is a statement about the empty set. At least I don't think you can find me any real number such that 0 > x > 4. I'll assume you meant 0 < x < 4 ;-)

In clearer term , if you take any two elements of R that result(sum) in 4 and multiply them , you won't find a bigger one than 2 × 2= 4.Same if you take 6 as an exemple , the largest will be 3 × 3 = 9.If I proved that , it would prove the theorem since $\frac{4}{4} = 1$ and all others denominator would be smaller , resulting in a larger number than 1.

That's a good approach. I don't know if you have done anything with quadratics yet, but note that y = x(4 - x) is a parabolic graph with zeroes at x = 0 and x = 4 which means that it has an extreme value right in the center at x = 2. (Try plotting it, you can use WolframAlpha if you don't know how to do this by hand yet).
How to prove that $x(4 - x) \le 4$ for all $0 < x < 4$ is a bit trickier if you have not taken analysis yet, in that case the "handwaiving" argument that x = 2 is a top of the graph is probably acceptable.

 

[reenmachine]

I'm sure that's not the theorem, because this is a statement about the empty set. At least I don't think you can find me any real number such that 0 > x > 4. I'll assume you meant 0 < x < 4 ;-)
That's a good approach. I don't know if you have done anything with quadratics yet, but note that y = x(4 - x) is a parabolic graph with zeroes at x = 0 and x = 4 which means that it has an extreme value right in the center at x = 2. (Try plotting it, you can use WolframAlpha if you don't know how to do this by hand yet).
How to prove that $x(4 - x) \le 4$ for all $0 < x < 4$ is a bit trickier if you have not taken analysis yet, in that case the "handwaiving" argument that x = 2 is a top of the graph is probably acceptable.

Yep it was a typing mistake at the beginning.0 < x < 4 is the correct statement , I apologize for that.

I saw your post after my proof attempt in the homework forum , here's the link https://www.physicsforums.com/showthread.php?t=703655

I have very little experience with quadratic.

thank you!