Question about proof from a guy with a highschool education

[reenmachine]

To continue with post 681.

No, the relation partitions the set into equivalence classes. Then we focus on the set of equivalence classes $\mathbb Z/\!\sim\,=\{[0],[1],[3]\}$ instead. Since we just defined this set, there's no addition operation defined on it yet. So we define one like this: For all $n,m\in\{0,1,2\}$, we define [n+m] by $[n]+[m]=[n+m]$.

Did you meant 0,1,2 instead of 0,1,3 at the beginning of this part?

You say that you define an addition operation with $\forall n , m \in \{0,1,2\}$ we define [n+m] by $[n]+[m]=[n+m]$.

suppose [3]+[7]=[3+7]=[10].How did we define that [10]=[7]=[4]=[1] here? Is it with our already defined $\sim$?

For clearness here , can $\sim$ means different kind of equivalence relations?

We can define addition modulo 3 on the set S={0,1,2} by saying that n+m (where + denotes the operation we're trying to define) is the unique k in S such that [k]=[n+m] (where + denotes the usual addition operation on the integers).

You say n+m is the unique k in S.This confuses me because 3+4 (with + being unknown) would be the unique k in S such that [k]=[7] since the second + means addition.How is there any 7 in k? Yes I understand that [1]=[7] because [1] = $\{...-2,1,4,7,10...\}$ , but I don't understand how our definition of this whole thing implied that you had to make a connection between the three sets of integers that gives multiple of 3 if you substract one to another and equivalence class such as [1].

We have found a "thing" that, except for notation, is "just like" some other thing. There are some fancy mathematical terms for this. You don't have to learn them now, but I guess it can't hurt if I mention them. The "things" we're working with here are called groups, and the technical way to say that the first one is "just like" the other one is to say that these groups are isomorphic.

Very interesting.I guess isomorphic groups are part of the beauty of math :D

It follows from the definitions of [n] and ~. [4] is the set of all integers that differ from 4 by an integer multiple of 3. [1] is the set of all integers that differ from 1 by an integer multiple of 3. It's pretty obvious that they are the same, and it's easy to prove it.

This part might answer some of my previous questions , but I'm not sure.So the definition of $\sim$ is one of the first assumptions we have in all of this right?

thank you once again man!

 

[Fredrik]

We now want to prove that $[x]\cap[y]\neq\varnothing\rightarrow[x]=[y]$.Suppose $[x]\cap[y]\neq\varnothing$.Let $z \in [x]$ be arbitrary.This implies that $z \sim x$.From our assumption we know that $\exists m \in [y]$ such that $m \in [x]$.This implies that $m \sim x$ and $m \sim y$.Since $\sim$ is symmetric and transitive , we have that $x \sim y$ and $z \sim y$.This implies that $z \in [y]$.This implies that $[x] = [y]$.

Looks good. I know I said that you don't have to explain why it's sufficient to prove $[x]\subseteq[y]$, but you should mention that it's sufficient, so that your readers know that this is the argument you're making. So the final sentence should be replaced with something like this: This implies that $[x]\subseteq [y]$. Since x and y are arbitrary elements of X such that $[x]\cap[y]\neq\varnothing$, it also follows that $[y]\subseteq [x]$, and therefore that $[x]=[y]$.

Alternatively: This implies that $[x]\subseteq [y]$. Similarly, we can prove that $[y]\subseteq [x]$. These results imply that $[x]=[y]$.

That "similarly" comment should be enough to get the reader to look at what you just did and notice that the proof still holds if we swap x and y.

 

[Fredrik]

Did you meant 0,1,2 instead of 0,1,3 at the beginning of this part?

Yes. (How did I manage to type a 3 there? )

You say that you define an addition operation with $\forall n , m \in \{0,1,2\}$ we define [n+m] by $[n]+[m]=[n+m]$.

I meant to say that we define [n]+[m] this way. [n+m] is already defined, and we're using that to define [n]+[m].

suppose [3]+[7]=[3+7]=[10].How did we define that [10]=[7]=[4]=[1] here? Is it with our already defined $\sim$?

For clearness here , can $\sim$ means different kind of equivalence relations?

All of this is with ~ meaning "is congruent modulo 3". To see that [10]=[1] for example, let $n\in[10]$ be arbitrary. Let m be an integer such that n-10=3m. We have n-1 = n-10+9 = 3m+3·3 = 3(m+3). Since m+3 is an integer, this implies that n~1. This implies that $n\in[1]$. And we can prove that every element of [1] is an element of [10] in a similar way.

You say n+m is the unique k in S.This confuses me because 3+4 (with + being unknown) would be the unique k in S such that [k]=[7] since the second + means addition.How is there any 7 in k? Yes I understand that [1]=[7] because [1] = $\{...-2,1,4,7,10...\}$ ,

First of all, I should mention again that this is an unnecessarily complicated way to define addition modulo 3 on S. This stuff with equivalence classes is a good way to define the other group {[0],[1],[2]}, which is isomorphic to S. But it's certainly not necessary to use that group to define the addition operation on S. I'm saying that we can do it this way, not that it's one of the easier ways.

Now, regarding what I said about how to do it. I said that for all n,m in S, we define n+m (where + is the addition operation we're trying to define) as the unique k in S such that [k]=[n+m] (where + is the usual addition operation on the integers). Since neither 3 nor 4 is in S, this does not define 3+4. It does however define 2+1 for example. 2+1 is the unique k in S such that [k]=[2+1]=[3]. Since [0]=[3], [1]≠[3] and [2]≠[3], that k is 0. So the definition tells us that 2+1=0.

This part might answer some of my previous questions , but I'm not sure.So the definition of $\sim$ is one of the first assumptions we have in all of this right?

It does, and yes it is.

 

[reenmachine]

Looks good. I know I said that you don't have to explain why it's sufficient to prove $[x]\subseteq[y]$, but you should mention that it's sufficient, so that your readers know that this is the argument you're making. So the final sentence should be replaced with something like this: This implies that $[x]\subseteq [y]$. Since x and y are arbitrary elements of X such that $[x]\cap[y]\neq\varnothing$, it also follows that $[y]\subseteq [x]$, and therefore that $[x]=[y]$.

Alternatively: This implies that $[x]\subseteq [y]$. Similarly, we can prove that $[y]\subseteq [x]$. These results imply that $[x]=[y]$.

That "similarly" comment should be enough to get the reader to look at what you just did and notice that the proof still holds if we swap x and y.

Ok understood.So while I don't have to completely write the proof in both directions (in 2 paragraphs) because the dummy variables are interchangeable , it's good to remind it to the reader.

Just a curiosity question , when you are reaching the level where only good mathematicians will be able to read your proofs , is those kind of "reminders" necessary?

 

[Fredrik]

Just a curiosity question , when you are reaching the level where only good mathematicians will be able to read your proofs , is those kind of "reminders" necessary?

They're probably not necessary then, but I think it's never a bad idea to include them.

 

[reenmachine]

I meant to say that we define [n]+[m] this way. [n+m] is already defined, and we're using that to define [n]+[m].

Understood.

All of this is with ~ meaning "is congruent modulo 3". To see that [10]=[1] for example, let $n\in[10]$ be arbitrary. Let m be an integer such that n-10=3m. We have n-1 = n-10+9 = 3m+3·3 = 3(m+3). Since m+3 is an integer, this implies that n~1. This implies that $n\in[1]$. And we can prove that every element of [1] is an element of [10] in a similar way.

That's awesome.

It seems my doubts about when to assume the definition of $\sim$ was a recurrent problem so I'm glad to understand it now.

Now, regarding what I said about how to do it. I said that for all n,m in S, we define n+m (where + is the addition operation we're trying to define) as the unique k in S such that [k]=[n+m] (where + is the usual addition operation on the integers). Since neither 3 nor 4 is in S, this does not define 3+4. It does however define 2+1 for example. 2+1 is the unique k in S such that [k]=[2+1]=[3]. Since [0]=[3], [1]≠[3] and [2]≠[3], that k is 0. So the definition tells us that 2+1=0.

Ok ok ok , so we use the equivalent classes to single out which $k \in S$ will have a $\sim$ with the integer n+m.

So if [2+2]=[4] , then by using the definition of the equivalence class we know that [4] = [1].So $1=k$.

thank you!

 

[Dmobb Jr.]

Yes it is important to write a lot of proofs for proactice. It is also, important, however to read a lot of proofs. Go to the library (preferably of a college if you can) and check out a book on algebra or set theory (or anything else). Just reading the proofs in the book will teach you farely well.

Edit: Did not reallize there was another 41 pages that I did not read so sorry if this is totally off topic.

 

[reenmachine]

Couples of comments about lists.

"Elements" of lists are called entries.List , contrary to sets , have to be in a particular order and can have repeated entries (if repetition is allowed).

If we have to create a length 3 list from the set $\{1,2,3,4\}$ with repetitions allowed , then to calculate the number of possible lists we just do $4(4)(4) = 64$.If repetition aren't allowed , then we do $4(3)(2) = 24$.If we want to know the number of possible lists containing a single 3 with repetition NOT allowed , then we do $3(2)(3)=18$ the last $(3)$ being the number of spots 3 can have in the order.If we want to know how many lists you can create using 1 (with repetition allowed) , then you calculate the number of list without 1 with $3(3)(3) =27$ and you subtract that result from all possible list $4(4)(4)=64$ , so $64-27=37$.So 37 possible lists using 1 as an entry.

Does that sound about right?

thank you!

 

[Fredrik]

Sounds good to me.

 

[reenmachine]

Sounds good to me.

Thank you!

 

[reenmachine]

Suppose the set $\{ A,B,C,D,E \}$.I want to find the number of lenght-5 lists made from this set that have at least one letter repeated.

My guess is I need to calculate the total amount and substract the amount of lists using all different letters from it.

$5(5)(5)(5)(5) - 5(4)(3)(2)(1)$ , $3125 - 120 = 3005$ lists with at least one letter repeated.

any thoughts on that?

thank you!

 

[Fredrik]

That sounds good too. But you should post textbook-style problems in the homework forums.

 

[reenmachine]

I'm back

Vacation for 2 weeks !

 

[reenmachine]

Picking up where I left off:

Since we are asked to count none-repetitive lists so many times , we can use factorials to handle the counting.

If I understood factorials correctly (in relation to this counting list concept) , $n!$ gives us the total amount of possible none-repetitive lists created from $n$ number of elements.

So both $0!$ and $1!$ should give us 1 list because of the empty list for $0!$.

The book of proof introduces the following generalized formula: $n! = n \cdot (n-1)!$

The formula works but I wonder how useful it is once there's a lot of elements.If you don't know what $(n-1)!$ is you are condemned to repeat the formula until you know what it is.

(post in progress...)

Since the length $k$ of lists isn't always the same , they introduce the formula $n(n-1)(n-2) \cdots (n-k+1)$ to find the number of none-repetitive lists of length $k$ given $n$ symbols or elements.

So if $n=5$ and you want to create none-repetitive length 3 lists , you can do $5 \cdot 4 \cdot 3$ and you stop there because of $(n-k+1)$ being $(5-3+1) = 3$ so the answer is $5 \cdot 4 \cdot 3 = 60$.So there's 60 non-repetitive lists of length 3 if you use 5 elements.

Just after that they introduce something I'm a little bit confused about at first glance.

Following their introduction of the formula $n(n-1)(n-2) \cdots (n-k+1).$ , they state:

Notice that by cancellation this value can also be written as

$\frac{n(n-1)(n-2) \ \cdots \ (n-k+1)(n-k)(n-k-1) \ \cdots \ 3 \cdot 2 \cdot 1}{(n-k)(n-k-1) \ \cdots \ 3 \cdot 2 \cdot 1} = \frac{n!}{(n-k)!}$

My confusion is probably related to the notation.

From my example:

$\frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1}= \frac{5!}{2!}=\frac{120}{2}=60$

The part I'm confused about is the $(n-k-1) \cdots 3 \cdot 2 \cdot 1$ in:

$\frac{n(n-1)(n-2) \ \cdots \ (n-k+1)(n-k)(n-k-1) \ \cdots \ 3 \cdot 2 \cdot 1}{(n-k)(n-k-1) \ \cdots \ 3 \cdot 2 \cdot 1} = \frac{n!}{(n-k)!}$

The $3 \cdot 2 \cdot 1$ at the end , does it mean that you continue in the $(n-k)(n-k-1)$ multiplication sequence until $(n-k-1)=1$ or $(n-k)=1$ or $(n-k-x)=1$ with $x \in \mathbb{N}$ and then you stop?

I ask because if you use 4 elements and a lenght-3 list , $(n-k-1)$ is $(4-3-1)=0$ and then you end up with $\frac{0}{0}$.So in this example , it would mean that you have to stop at $(n-k)$ which is $(4-3)=1$ is that correct?

thank you!

 

[Fredrik]

If I understood factorials correctly (in relation to this counting list concept) , $n!$ gives us the total amount of possible none-repetitive lists created from $n$ number of elements.

Right, because there are n ways to pick the first entry, n-1 ways to pick the second one, and so on.

The book of proof introduces the following generalized formula: $n! = n \cdot (n-1)!$

The formula works but I wonder how useful it is once there's a lot of elements.If you don't know what $(n-1)!$ is you are condemned to repeat the formula until you know what it is.

It's especially useful when there's a lot of elements. Suppose that you want to prove that a statement P(n) is true for all non-negative integers n. You obviously can't do this one statement at a time: P(0), P(1), ... What you do instead is to prove the following two statements:

P(0)
For all non-negative integers n, if P(n) then P(n+1).

If P(n) is a statement that involves n!, you will find the formula (n+1)!=(n+1)n! extremely useful when you need to prove the second statement above.

But the formula isn't introduced just to be useful in proofs and calculations. It gives us a way to unambiguously state the definition of n! for all $n\in\mathbb N$. First we define 0! by $0!=1$, and then, for each $n\in\mathbb Z^+$, we define $n!$ by $n!=n(n-1)!$.

Edit: I see now that the book "defines" n! as the number of non-repetitive lists that can be made from n symbols. I don't like that definition. The one I just stated is standard, and simpler.

So if $n=5$ and you want to create none-repetitive length 3 lists , you can do $5 \cdot 4 \cdot 3$ and you stop there because of $(n-k+1)$ being $(5-3+1) = 3$ so the answer is $5 \cdot 4 \cdot 3 = 60$.So there's 60 non-repetitive lists of length 3 if you use 5 elements.

5 ways to choose the first element, 4 ways to choose the second, 3 ways to choose the third. So 5·4·3=60.

Just after that they introduce something I'm a little bit confused about at first glance.

Following their introduction of the formula $n(n-1)(n-2) \cdots (n-k+1).$ , they state:

For example,
$$5\cdot 4\cdot 3=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{2\cdot 1}=\frac{5!}{2!}.$$ With n=5 and k=3,
$$5\cdot 4\cdot 3=n(n-1)(n-2) =n\cdots(n-k+1) =\frac{n\cdots(n-k+1)(n-k)\cdots 1}{(n-k)\cdots 1} =\frac{n!}{(n-k)!} =\frac{5!}{2!}.$$

My confusion is probably related to the notation.

From my example:

$\frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1}= \frac{5!}{2!}=\frac{120}{2}=60$

The part I'm confused about is the $(n-k-1) \cdots 3 \cdot 2 \cdot 1$ in:
The $3 \cdot 2 \cdot 1$ at the end , does it mean that you continue in the $(n-k)(n-k-1)$ multiplication sequence until $(n-k-1)=1$ or $(n-k)=1$ or $(n-k-x)=1$ with $x \in \mathbb{N}$ and then you stop?

I ask because if you use 4 elements and a lenght-3 list , $(n-k-1)$ is $(4-3-1)=0$ and then you end up with $\frac{0}{0}$.So in this example , it would mean that you have to stop at $(n-k)$ which is $(4-3)=1$ is that correct?

Yes, the notation looks weird when n-k-1 ≤ 3. Since the numerator looks like a product of at least nine factors, it's also weird if n<9. This is a problem with the notation, but I think it's pretty common to ignore that and use a notation that only makes sense for certain values of n and k.

I think that now that you know that the notation isn't supposed to make sense, it will make perfect sense.

 

[reenmachine]

It's especially useful when there's a lot of elements. Suppose that you want to prove that a statement P(n) is true for all positive integers n. You obviously can't do this one statement at a time: P(0), P(1), ... What you do instead is to prove the following two statements:

First of all , just so it's completely clear , here the notations means: P(n) = statement about n?

P(0)
For all positive integers n, if P(n) then P(n+1).

I'm not sure I understand what P(0) is doing there.Just so we're clear again , did you mean that you first have to prove P(0) , and then you have to prove that for all positive integers n , $P(n) \rightarrow P(n+1)$ , proving that if P(0) is true , then P(1) is true , which implies that P(2) is true and on and on...? I'm confused by this because 0 isn't a positive integer as far as I know?!?

If P(n) is a statement that involves n!, you will find the formula (n+1)!=(n+1)n! extremely useful when you need to prove the second statement above.

So the formula is extremely useful to connect a statement about a specific number to another larger set of numbers? What I meant in my original post was that the formula wasn't very useful to find what $n!$ is if $n$ is a large integer.

But the formula isn't introduced just to be useful in proofs and calculations. It gives us a way to unambiguously state the definition of n! for all $n\in\mathbb N$. First we define $0!=0$, and then, for each $n\in\mathbb Z^+$, we define $n!$ by $n!=n(n-1)!$.

What do you mean by we define $0!=0$?

For example,
$$5\cdot 4\cdot 3=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{2\cdot 1}=\frac{5!}{2!}.$$ With n=5 and k=3,
$$5\cdot 4\cdot 3=n(n-1)(n-2) =n\cdots(n-k+1) =\frac{n\cdots(n-k+1)(n-k)\cdots 1}{(n-k)\cdots 1} =\frac{n!}{(n-k)!} =\frac{5!}{2!}.$$

Yeah it's much clearer that way.

Yes, the notation looks weird when n-k-1 ≤ 3. Since the numerator looks like a product of at least nine factors, it's also weird if n<9. This is a problem with the notation, but I think it's pretty common to ignore that and use a notation that only makes sense for certain values of n and k.

I think that now that you know that the notation isn't supposed to make sense, it will make perfect sense.

Pretty sure I get it now

Basically they gave us this notation as an example of what to do if you're dealing with larger numbers.

thank you Fredrik!

I'm glad to be back!

 

[Fredrik]

First of all , just so it's completely clear , here the notations means: P(n) = statement about n?

Yes.

What do you mean by we define $0!=0$?

D'oh. Typo. I meant to say that we define 0! by 0!=1.

I'm not sure I understand what P(0) is doing there.Just so we're clear again , did you mean that you first have to prove P(0) , and then you have to prove that for all positive integers n , $P(n) \rightarrow P(n+1)$ , proving that if P(0) is true , then P(1) is true , which implies that P(2) is true and on and on...? I'm confused by this because 0 isn't a positive integer as far as I know?!?

OK, I see I got more details wrong in my statement. I will edit it above, and include a new explanation below. It looks like you got the general idea anyway.

I include 0 in $\mathbb N$, and use the notation $\mathbb Z^+$ for the positive integers. I should have mentioned that, since the book uses the notation $\mathbb N$ for the positive integers.

The proof technique I'm talking about is called "induction". It's chapter 10 in Book of proof. The idea is that you can prove $\forall n\in\mathbb N~P(n)$ by proving the two statements $P(0)$ and $\forall n\in\mathbb N~P(n)\to P(n+1)$. This is useful when you're unable to prove $P(n)$ for an arbitrary $n\in\mathbb N$.

Similarly, you can prove $\forall n\in\mathbb Z^+~P(n)$ by proving the two statements $P(1)$ and $\forall n\in\mathbb Z^+~P(n)\to P(n+1)$.

So the formula is extremely useful to connect a statement about a specific number to another larger set of numbers? What I meant in my original post was that the formula wasn't very useful to find what $n!$ is if $n$ is a large integer.

I would say that since it's part of the definition of n! (the other part is the statement 0!=1), the formula is always useful. I mentioned induction because when you prove that P(n) implies P(n+1), you would typically only have to use the formula once. (This is of course assuming that P(n) is, for all n, a statement that involves n!).

 

[reenmachine]

OK, I see I got more details wrong in my statement. I will edit it above, and include a new explanation below. It looks like you got the general idea anyway.

I include 0 in $\mathbb N$, and use the notation $\mathbb Z^+$ for the positive integers. I should have mentioned that, since the book uses the notation $\mathbb N$ for the positive integers.

The proof technique I'm talking about is called "induction". It's chapter 10 in Book of proof. The idea is that you can prove $\forall n\in\mathbb N~P(n)$ by proving the two statements $P(0)$ and $\forall n\in\mathbb N~P(n)\to P(n+1)$. This is useful when you're unable to prove $P(n)$ for an arbitrary $n\in\mathbb N$.

Similarly, you can prove $\forall n\in\mathbb Z^+~P(n)$ by proving the two statements $P(1)$ and $\forall n\in\mathbb Z^+~P(n)\to P(n+1)$.

Yeah this is what I had in mind , thank you!

I would say that since it's part of the definition of n! (the other part is the statement 0!=1), the formula is always useful. I mentioned induction because when you prove that P(n) implies P(n+1), you would typically only have to use the formula once. (This is of course assuming that P(n) is, for all n, a statement that involves n!).

Very clear again thanks!

 

[reenmachine]

Counting subset

They introduce a weird notation that ressemble a fraction but without the horizontal line in the middle.I won't use it unfortunately because I don't know how to write it in LaTeX.

Anyway they use it to introduce a new formula to find the number of possible subsets created from a sets with $n$ number of elements and choosing $k$ number of elements from it.

They illustrate the formula using the set $\{a,b,c,d,e\}$ and taking 3 elements from it , which would give us 10 subsets possible.Then they tell us to use each subsets (containing 3 elements each) and to verify how many none-repetitive lists you could produce from these 3 elements.The answer is obviously 3!= 6 , and with this we can also do $6 \cdot 10$ to know how many lenght-3 none-repetitive list we can produce with the entire earlier set $\{a,b,c,d,e\}$.This is the same as $\frac{5!}{(5-3)!}$ and the answer is 60.With this you can use the formula $\frac{n!}{k!(n-k)!}$ to find the number of possible subsets created from a set with $n$ number of elements and choosing $k$ number of elements from it.It works because you divided (from our exemple) 3! from both $\frac{5!}{(5-3)!}$ and $3! \cdot 10$.

This is all simple enough , but I would like to clarify one thing:

Suppose you have: $\frac{7!}{2!(7-2)!} = \frac{7!}{2!5!}$.

Does it matter which factorial you choose to cancel in the denominator?

Exemple: $\frac{7 \cdot 6 \cdot 5!}{2!5!} = \frac{7 \cdot 6}{2!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2!}{2!5!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3}{5!}$.

I've done the calculations and it seems correct.

I know this is very trivial but I like to always see clearly in my computations.Basically I'm not sure if I have any real question in this post as I kind of thought it out while I was typing so sorry about that

 

[micromass]

Counting subset

They introduce a weird notation that ressemble a fraction but without the horizontal line in the middle.I won't use it unfortunately because I don't know how to write it in LaTeX.

That is called a "binomial coefficient". The LaTeX code is

\binom{n}{k}

For $\binom{n}{k}$.

Does it matter which factorial you choose to cancel in the denominator?

No, it doesn't matter.

 

[reenmachine]

That is called a "binomial coefficient". The LaTeX code is

\binom{n}{k}

For $\binom{n}{k}$.



No, it doesn't matter.

Thank you! Very appreciated!

 

[Fredrik]

Does it matter which factorial you choose to cancel in the denominator?

Since a cancellation doesn't change the value of the fraction, it doesn't matter what you cancel (as long as it's not zero).

 

[reenmachine]

What do you guys think I should do when I'm facing exercises which are using a concept Y I don't know anything about to verify my knowledge of a different concept X that is taught in the book?

Should I just skip them? This is a little bit frustrating sometimes but it's something I have to accept since I decided to learn some mathematics that are ahead of where I officially am academically.

 

[reenmachine]

The book of proof introduces the pattern $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$ for any integers $n$ and $k$ with $0<k≤n$.

Then they say that the set $A= \{0,1,2,3, \cdots , n\}$ has n+1 elements (because of 0?).So $\binom{n+1}{k}$ equals the number of $k$ elements subsets of $A$.Then they say that the subsets can be divided into two categories , those with 0 and those without 0.This is where I'm a little bit confused.They say that $\binom{n}{k-1}$ equals the number of $k$ elements subsets of A that contains 0.I can compute it , but I'm not sure I get it yet.

When $k$ becomes $k-1$ , is it because you already know that 0 will be one element selected from A? So basically you do $\binom{n}{k-1}$ to find the amount of possible combinations of $k-1$ elements that can be connected to 0 as a subset , and since it's not repetitive , you transform $n+1$ into $n$ because 0 is already taken?

Coming back to $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$ , then $\binom{n}{k}$ is just the subsets without 0 which you add to your amount of subsets with 0 , all of this to obtain the number of subsets taking $k$-elements from a set with $n+1$ elements?

As for the "big picture" of this pattern , was the intuition here simply to "isolate" the consequences on the number of subsets (created by $+1$ in $n+1$) with $\binom{n}{k-1}$?

After that they illustrate it using some kind pascal triangle with a bunch of binomial coefficient instead of integers.From what I saw this meant that the addition of two binomial coefficients placed side by side in the triangle results in the binomial coefficient placed under both.

edit: Just saw that the results of the binomial coefficients are placed at the same spot as pascal's triangle integers in the triangle and they are equal.Is this why the pascal triangle was created in the first place?

thank you!

 

[1MileCrash]

Hey, I'll try to answer some of your concerns.

The book of proof introduces the pattern $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$ for any integers $n$ and $k$ with $0<k≤n$.

Then they say that the set $A= \{0,1,2,3, \cdots , n\}$ has n+1 elements (because of 0?)

Yep, it's because 0 is also an element of that set.

So $\binom{n+1}{k}$ equals the number of $k$ elements subsets of $A$.

That's right, it is the number of subsets of A that have a cardinality of k.

The way I think about it as this (if you don't know this, these binomial coefficients are read "n choose k" so what I'm about to say is obvious)

$\binom{n+1}{k}$

is the number of ways I can select k elements from n+1 elements. For example, if we have the set {a,b} and I want to choose 2 elements, there's only one choice, to pick a, and b. So 2 choose 2, or the binomial coefficient $\binom{2}{2}$ is 1, and in fact $\binom{n}{n}$ is 1.

This also provides a very intuitive understanding for
$\binom{n}{k} = \binom{n}{n-k}$

Because there is no difference between choosing to "take" k elements and choosing to "leave" n-k elements, so the number of ways to choose k or n-k elements must be the same (sorry if this was covered already.)

You can choose to think of it as the "number of subsets" if you like, but in dealing with probability or applications, it is helpful for me to think of it in the terms of number of ways that something can happen.

For example, the number of possible poker hands is $\binom{52}{5}$, because there are 52 cards and a poker hand consists of 5 cards. So when you get a hand of poker, you got one of the possible subsets of the 52 cards that is 5 cards large.

Then they say that the subsets can be divided into two categories , those with 0 and those without 0.This is where I'm a little bit confused.They say that $\binom{n}{k-1}$ equals the number of $k$ elements subsets of A that contains 0.I can compute it , but I'm not sure I get it yet.

When $k$ becomes $k-1$ , is it because you already know that 0 will be one element selected from A? So basically you do $\binom{n}{k-1}$ to find the amount of possible combinations of $k-1$ elements that can be connected to 0 as a subset , and since it's not repetitive , you transform $n+1$ into $n$ because 0 is already taken?

That's exactly right. 0 is kind of "put on reserve." The number of subsets that have a cardinality of k and contain 0, means that I am saying "0 is here, now pick the remaining k-1 elements of this set." The number of ways to pick the remaining elements is then $\binom{n}{k-1}$ , and that is the number of subsets that contain 0. You designated one of the elements as 0, then you select k-1 more elements, giving you a set of k elements.

Coming back to $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$ , then $\binom{n}{k}$ is just the subsets without 0 which you add to your amount of subsets with 0 , all of this to obtain the number of subsets taking $k$-elements from a set with $n+1$ elements?

Pretty much.

$\binom{n}{k-1}$ means "the number of ways to pick k-1 elements from n elements." We are only picking k-1 elements because the 0 is already in every set we are considering, and it can't appear twice.

$\binom{n}{k}$ means "the number of ways to pick k elements from n elements." So the n elements being considered here are the nonzero elements only. That is where our choices can be made, because every single set that contains 0 is already accounted for in the first binomial coefficient.

As for the "big picture" of this pattern , was the intuition here simply to "isolate" the consequences on the number of subsets (created by $+1$ in $n+1$) with $\binom{n}{k-1}$?

thank you!

If I understand you correctly, I think that is a fitting interpretation.

 

[reenmachine]

Hey, I'll try to answer some of your concerns.

Thank you for your help!

Yep, it's because 0 is also an element of that set.

Yeah as I wrote the rest of the post it became pretty clear but I didn't edit it.

This also provides a very intuitive understanding for
$\binom{n}{k} = \binom{n}{n-k}$

Because there is no difference between choosing to "take" k elements and choosing to "leave" n-k elements, so the number of ways to choose k or n-k elements must be the same (sorry if this was covered already.)

Very clear! Another way to put it would be: $\binom{n}{k} = \frac{n!}{k!(n-k)!} = \binom{n}{n-k} = \frac{n!}{(n-k)!(n-(n-k))!}$ is that correct? Since $(n-(n-k)) = k$ , we have $k!(n-k)! = (n-k)!k!$.

For example, the number of possible poker hands is $\binom{52}{5}$, because there are 52 cards and a poker hand consists of 5 cards. So when you get a hand of poker, you got one of the possible subsets of the 52 cards that is 5 cards large.

Nice exemple.But good lord , some people still play 5-card draw poker?

That's exactly right. 0 is kind of "put on reserve." The number of subsets that have a cardinality of k and contain 0, means that I am saying "0 is here, now pick the remaining k-1 elements of this set." The number of ways to pick the remaining elements is then $\binom{n}{k-1}$ , and that is the number of subsets that contain 0. You designated one of the elements as 0, then you select k-1 more elements, giving you a set of k elements.

Very clear!

Thanks a lot for taking the time to help me!

 

[1MileCrash]

Very clear! Another way to put it would be: $\binom{n}{k} = \frac{n!}{k!(n-k)!} = \binom{n}{n-k} = \frac{n!}{(n-k)!(n-(n-k))!}$ is that correct? Since $(n-(n-k)) = k$ , we have $k!(n-k)! = (n-k)!k!$.

Yes, when you let the choice be n-k instead of k, you can quickly see that the only thing that happens is that the multiplication in the denominator flips.

It's one of those cool things in math where we intuitively believe something about a physical thing (that choosing to "take" n donuts from a box and choosing to "leave" n-k donuts from a box are really the same thing) and our little algebra symbols readily agree.

 

[verty]

The book of proof introduces the pattern $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$ for any integers $n$ and $k$ with $0<k≤n$.

This is known as Pascal's rule. See also Pascal's triangle.

 

[reenmachine]

I randomly ended up in this thread : https://www.physicsforums.com/showthread.php?p=4450910#post4450910 and thought it was interesting since I'm currently working on this.

I'm having some problems understanding what (a) is in that thread and if $n$ is assumed to be a positive integer right off the bat?

In trying to prove P(0) , I attempted:

We will attempt to prove that $\binom{n}{k}$ is an integer if $k=0$.

We know $\binom{n}{k}$ is equal to $\frac{n!}{k!(n-k)!}$.If $k=0$ , then we have $\frac{n!}{0!(n-0)!}$.Since 0!=1 , we have $\frac{n!}{1 \cdot n!} = \frac{n!}{n!} = 1$.

what are your thoughts on this? I'm still having trouble deciding what I can assume and what I have to prove.Do I have to prove that 0!=1?

(I understand I didn't prove the second part , just verifying with the first step , it's been a while since I wrote a proof.)

thank you!

 

[micromass]

I randomly ended up in this thread : https://www.physicsforums.com/showthread.php?p=4450910#post4450910 and thought it was interesting since I'm currently working on this.

I'm having some problems understanding what (a) is in that thread and if $n$ is assumed to be a positive integer right off the bat?

In trying to prove P(0) , I attempted:

We will attempt to prove that $\binom{n}{k}$ is a positive integer if $k=0$.

We know $\binom{n}{k}$ is equal to $\frac{n!}{k!(n-k)!}$.If $k=0$ , then we have $\frac{n!}{0!(n-0)!}$.Since 0!=1 , we have $\frac{n!}{1 \cdot n!} = \frac{n!}{n!} = 1$.

what are your thoughts on this?

Seems good.

I'm still having trouble deciding what I can assume and what I have to prove.Do I have to prove that 0!=1?

Depends on your definition of factorial. Most definitions will take $0! = 1$ into the definition, so you won't need to prove it.