and like "double up" on it, kind of
#discrete-math
mystic moss
weary tiger
yeah so it is included u right
mystic moss
here s is an arbitrary number less than n, right?
weary tiger
yeah, or equal to
mystic moss
that the first vertex chooses to "claim"
mystic moss
okay, cool. so s is an arbitrary number less than... n-k+1?
*or equal to, perhaps
does each column vertex need to claim at least one row vertex?
weary tiger
yep
everything needs at least 1 adjacency
per the original question
so this would be valid
mystic moss
okay, and everything being on the bottom line would also work
no
what i meant was all the row vertices connecting to just the first vertex would work
mystic moss
yeah, all the column vertices would be forced to connect to the last row vertex
weary tiger
ye ye ok then
mystic moss
also, this is remarkably like finding paths in a (n, k) grid
i might have mentioned that before oops
also each of the "corners" in the path can be deleted and it would still be a valid relation, right?
weary tiger
f(n,k) = Sum on all the valid s [ f(n-s+1,k-1) + ways 1st row vertex connects to first s column vertices ] BOOM that should be it
and then we just need the valid s and the ways for the 1st vertex
corners?
I think an edge can be deleted if and only if both its vertices are at least degree 2
mystic moss
ooh nice. the number of ways for the 1st vertex should just be 1 for any given s, right?
weary tiger
for like (1,1) right
mystic moss
and also, the second vertex doesn't need to claim the n-s+1th vertex. that's what i meant by "corner"
mystic moss
oops yeah i meant sth 😅
for like (1,1) right
here you're referring to the "corner" in the first diagram?
weary tiger
we can refer to the actual entries in the matrix you can overlay on these drawings
so yeah (1,1) always equals 1
mystic moss
where the indices start from one, right?
weary tiger
wait I think that "ways 1st row vertex connects to first s column vertices" is always 1
Yeah
POG
mystic moss
haha nice
weary tiger
f(n,k) = Sum on all the valid s [ f(n-s+1,k-1) + 1 ]
mystic moss
but also do you get the corners thing?
weary tiger
what do you mean? I just defined the corners as "1"s on the matrix
mystic moss
hm okay let me pull up the diagram again
here i mean the edge from the second column vertex to the second row vertex
that forms a "corner" in the "path" of 1s from the top left to bottom right
mystic moss
hmm kind of? it's an unnecessary edge (i.e. a "double")
like here the third column vertex-fifth row vertex edge is also a "corner"
mystic moss
yes, and note that it doesn't form a complete path
and also, we won't get this configuration with the recurrence relation above i believe
mystic moss
hm i don't think we defined what happens when k=1 perhaps
scarlet current
if two sets have the same elements are they subsets of each other?
mystic moss
but at the point at which k=1, we'd just take all of the row vertices left and connect it with that vertex, right?
weary tiger
yeah
mystic moss
okay, so here s=1
and we have n-s+1=2 vertices left for the last vertex
so both vertices would connect to the last vertex
which is not what we have up there
vital dewBOT
zd:
weary tiger
f(2,2) = 2 + f(2,1) + f(1,1) = 2 + 1 + 1 = 4
I think it might be good!!!! holy shit
WAIT
I have the short term memory of a goldfish, or maybe a brick wall
mystic moss
you seem to be very hard on yourself
weary tiger
I am just making light of myself to be clear to you that I did something wrong but that maybe true ;-;
there are just some days where I can't be trusted mathematically lmao
mystic moss
lol relatable. but also where did we get the +1 from btw?
if it was the "number of ways to connect the vertices" shouldn't it be *1?
weary tiger
wait so it's a product?
mystic moss
lol 😅 but we still don't take into account the duplicates
weary tiger
$f(n,k) = \sum_{s=1}^{k} f(n-s+1,k-1) $
vital dewBOT
zd:
weary tiger
I'm not sure how they're not being accounted for
mystic moss
well in this case we get f(2, 2) is 2
mystic moss
yeah i think for every left-hand corner we can take an edge away or smth like that
weary tiger
f(n,k) = Add up all the resulting ways to connect vertices after choosing s
given s there is only one possibility for the first row, so then you have f(n-s+1,k-1) ways
ahhh why is that wrong
it definitely is
mystic moss
because the second vertex can choose to duplicate the last edge
or last vertex, rather
it can choose to do n-s+1 or just n-s
or smth like that
mystic moss
yeah i believe so
when n=1, all of the rest of the vertices in S must double up
okay, so we have the end cases
weary tiger
they're separate cases so f(n-s+1,k-1)+f(n-s,k-1) inside the sum?
mystic moss
f(1, k) = 1 and f(n, 1) = 1
hm, are they entirely separate?
i think they're just the same thing perhaps, but just X2
or *2, because the x is rather ambiguous
mystic moss
oh you mean the sth vertex? but it's already accounted for, the rest of the population doesn't care if the k-1th vertex is connected to it or not
we just care for counting purposes
weary tiger
I was about to agree but
mystic moss
wait i see. it may be the case that if we take f(n-s+1, k-1), we're now also counting all the ways in which the k-2th column vertex can connect to the sth row vertex, and so on
weary tiger
if you leave in the sth vertex for the next recursion the other k-1 could still potentially connect to it, not just the k-1th alone
we on the same page I think
mystic moss
yeah. i do think this is overcounting a bit though
mystic moss
hm what relation are we using as of rn?
weary tiger
$f(n,k) = \sum_{s=1}^{k} \left[f(n-s+1,k-1) + f(n-s,k-1)\right]$
mystic moss
sounds about right. also the solution works
vital dewBOT
zd:
weary tiger
YAY
mystic moss
for 2, 2
weary tiger
imagine doing that all on that kids uni entrance exam
as a 4th year undergraduade math major myself that would be wild
I think we are just 
here in the US
mystic moss
loll yeah 😔
but at least we don't have to stress as much for college apps
actually, debatable. but i'll never get to know for sure because i'm probably not going international for college
whereas people who come to the US get to compare
weary tiger
thinking about working to save up for a while after I get my bachelor's in May and get a master's abroad in Germany or Austria
mystic moss
good luck with that! incidentally, what kind of working?
weary tiger
might not be as good as UK or France or whatever but I want to be immersed in the language, culture etc
probably software engineering or something tangentially related
if the world were perfect I could do some math r&d stuff for a firm/the gov
mystic moss
r&d?
weary tiger
research and development, or anything like that
mystic moss
interesting. i bet you can still apply though, even if the world isn't perfect?
weary tiger
exaaaactly
fading abyss
software engineering as a math major?
i guess but you could look for a math role( like quant or research? )
weary tiger
My major is Computational Mathematics
I go basically as far into the CS track as 2nd/3rd year CS Majors do (they have a 5 year major)
So I have an actual software engineering class under my belt, database management, around 4 programming classes, the job market for mathematicians is ass at entry level I've heard if you can't program so I will just weasel my way into the job market for CS people LOL
mystic moss
nice. is a CS major more theoretical or more software? what does a computational mathematics major actually mean lol
weary tiger
it is kinda meaningless, just extra class requirements in the cs dept
I'm practically just a math major who can get better jobs 
mystic moss
lol well played 👏
weary tiger
Ted I think we did it btw
gritty crescent
Great!
weary tiger
ty for showing that problem it was fun
gritty crescent
Although I'm certain the solution would still be incomprehensible to me :p But I appreciate your efforts!
I might have one more...XD
weary tiger
it was $f(n,k) = \sum_{s=1}^{k} \left[f(n-s+1,k-1) + f(n-s,k-1)\right]$
vital dewBOT
zd:
mystic moss
^ yeah, you can read through the conversation to get an idea of the thought process
gritty crescent
Ah, that's why the question mentioned the recurrence relation should necessarily have a finite number of terms.
mystic moss
wait, huh?
weary tiger
how would u do that with an infinite sum 😂 ?
weary tiger
oh I'm guessing some interpolation magic
gritty crescent
Some combinatorics identity I vaguely remember
mystic moss
perhaps it meant that it doesn't need to be a closed form relation? 🤔
weary tiger
that would do the infinite sum maybe
gritty crescent
perhaps it meant that it doesn't need to be a closed form relation? 🤔
@mystic moss Maybe that, my memory could be betraying me here.
scarlet current
are all subsets R from cartesian product a relation? excluding the empty set?
also what does ⊂ indicate?
im unsure what the difference between ⊂ and ⊆ is
i know that ⊆ is used so A ⊆ B is A is subset of B
im unsure what the difference between ⊂ and ⊆ is
@scarlet current nvm this i understand the difference now
glass condor
subset and not equal.
gritty crescent
Yes, all relations are subsets of the cartesian product of the sets under consideration.
glass condor
However, in many cases people write ⊂ but mean ⊆.
scarlet current
ah ok thanks!
is the empty set a subset of the cartesian product of the sets? and if so then are they also a relation?
sour arrow
Empty set is a subset of any set
honest barn
Yeah that’s called the empty relation
It says literally nothing
Nothing is related to anything
sour arrow
Which by vacuous truth is an equivalence relation haha
analog vault
My proffesor said that this proof was incorrect. Can anyone help me understand why?
ember obsidian
@analog vault it's just incomprehensible. what's c? it's not clear at all how 1 leads to 2 or 2 leads to 3. try working different cases where the antecedent is true
feral shell
how to make C have only even numbers as the output from A?
spiral cradle
can someone tell me how this is possible?
vital dewBOT
Star_:
spiral cradle
oh ok thanks
tame hound
hi
can anyone help me with this asap?
A relation R is defined on Z by a R b if 5a − b is even.
(a) Prove that R is an equivalence relation.
(b) Describe the distinct equivalence classes resulting from R.
?
weary tiger
do you know what an equivalence relation is?
unravel all the definitions and you will be basically done
tame hound
alright thx
weary tiger
I might be totally wrong but you could think of the 15 couples as a row of 15 men and a row of 15 women stacked together
so there are 15! possible ways to stack the men in
and 20P15 for the women (I think?)
So it would be 15! * 20P15 = 15! 20!/(5! * 15!) = 20!/5!
cunning thistle
Ig you'll be counting extra with 20P15. Ig it should be 20C15
weary tiger
oop I said P but did C wtf is wrong with me
cunning thistle
Idw but i think 20C15 will also result in us counting extra cases. Not sure though so don't quote me on that
scarlet current
how do you prove de morgans law in propositional logic?
truth table?
is that the only way?
is this a proof for Show that if A⊆C and B⊆D, then A×B ⊆ C×D
@scarlet current also is this correct?
blissful basin
Idk if this is a part of Discrete Math but how to use the STTT?
bronze rain
What's STTT?
blissful basin
Shortened truth table technique@bronze rain
scarlet current
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
the distributive law can be proved two ways right
first is making A ∩ (B ∪ C) into set builder notation and then showing that it is equal to (A ∩ B) ∪ (A ∩ C).
and the other way is to show that the two expressions are subsets of each other right?
the first way is much faster, no?
pale epoch
it's essentially the same
serene tendon
nah i dont think its much faster but the second way is much cleaner imo
pale epoch
$A = B$ is just shorthand for $A \subseteq B \land B \subseteq A$
vital dewBOT
Lochverstärker:
pale epoch
so you essentially make the same claims both ways
just in the "shorter" version you condense it and make 2 claims at once at every step
scarlet current
what are the various ways to show logical equivalence again
truth table, rules of inference
for rules of inference you have to show Proposition 1 double arrow right Proposition 2 and Proposition 2 double arrow right Proposition 1 to show that the two are logically equivalent right?
you could also just symbolically show that they are logically equivalence with other established equivalence theorems right?
is that all three ways?
scarlet current
this is incomplete right?
i need to show it the other way around as well
correct?
near root
S, T are relations on P(|N) that are defined like this:
For X,Y C= |N
(X, Y) e S if and only if 1 e X symmetric difference Y or X=Y.
(X, Y) e T if and only if 1 !e X symmetric difference Y.
Show that S isn't an equivalence relation.
If it's an Or statement and there's an equal sign how come that is not and equivalence relation?
scarlet current
i need to show it the other way around as well
@scarlet current i only used biconditional tautologies in this so does that mean i dont need to show it the other way around? I only need to show both ways if i use at least one implication tautology right?
why do i need to show this the other way around
i dont use any implication tautologies here
cant this just be proved with steps 1-7?
stray reef
@scarlet current they're introducing a set here and using the letter I for its name
scarlet current
why is i an element of I
vital dewBOT
Ann:
scarlet current
oh so if this thing goes to like i=n and starts when i=1 would I be the set containing i, I, be {1,2,3,4,.....,n}?
stray reef
??
no, I is just an index set. it doesnt have to be a subset of N, it can literally be whatever
drifting sail
it can be whatever but in that particular case it indeed is {1,2,...,n}
errant bear
youd just say for i in I
errant bear
yeah, i mean you could use an index for it, but you probably wouldnt want/need to unless you have a specific reason to
quaint star
You would write $\sum_{i \in I} a_i$, and that would mean $a_2 + a_5 + a_7 + a_8 + a_9$
scarlet current
so if i is element of I and im using big U then it is the union of A2, A5, A7, A8, A9 right?
drifting sail
so if i is element of I and im using big U then it is the union of A2, A5, A7, A8, A9 right?
yep
scarlet current
ok thanks!
drifting sail
But again, I can be ANY set
this happens a lot in topology/real analysis, e.g. to write an open set $O$ as an union of open balls $O=\bigcup_{x\in O} B(x,\varepsilon_x)$ where $B(x,\varepsilon_x)\subset O$. Here $O$ could have pretty much any cardinality, perhaps the same as $\mathbb R$
vital dewBOT
bastian.uwu:
icy parcel
hey guys i have smthn i need to find it via formal proof but our dr said its impossible to solve can u help me do it ? i have noooooo idea how to
the c)
anyone?
<@&286206848099549185>
drifting sail
@icy parcel try by cases. What happens if $\neg p$ and $p\vee q$? What happens if $\neg r$ and $p\vee q$?
vital dewBOT
bastian.uwu:
drifting sail
(if you're required to do it in a "logical calculus" sort of way, proof by cases is a fancy way of saying that $(p\vdash r)\wedge(q\vdash r) \equiv (p\vee q \vdash r)$ I suppose)
vital dewBOT
bastian.uwu:
icy parcel
we should formal proove it
from the thing on the left
get to the conclusion on the right
@drifting sail
<@&286206848099549185>
sterile flint
i don't quite know if this is the right place to ask but does anyone know if there's a website that'll be able to expand this equation
errant bear
you could do it yourself
scarlet current
is an infinite set the set of all real numbers
pale epoch
no
serene basalt
how would you do that?
it would be like sum_{k1,k2,k3} x^{k1 + 2k2 + 5k3}, but that's not useful, how would we work out the coefficients?
oh i know how to do it
change it into geometric series 1/[(1-x)(1-x^2)(1-x^5)]
? 1/(-x^8 + x^7 + x^6 - x^5 + x^3 - x^2 - x + 1) + O(x^20)
%4 = 1 + x + 2*x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 5*x^6 + 6*x^7 + 7*x^8 + 8*x^9 + 10*x^10 + 11*x^11 + 13*x^12 + 14*x^13 + 16*x^14 + 18*x^15 + 20*x^16 + 22*x^17 + 24*x^18 + 26*x^19 + O(x^20)
not totally sure what the rule for the coefficients would be but its progress
I think they would fit some fibonacci type rule, but with more than 2 terms
sterile flint
it was originally a geometric series
scarlet current
Ai = {−i,−i + 1,...,−1,0,1,...,i − 1,i}.
why is the upside down big U of this -1,0,1?
shouldnt it be -i?
because A1 is -i
stray reef
what
A_1 = {-1, 0, 1} the way you defined it
i doesn't refer to the imaginary unit here
calm comet
so my descrete math teacher is being :(
im a highschooler btw
can you tell if a graph is planar based on only a set of a vertices and edges?
or i guess whats the formal definition of a face in graph theory
pale epoch
sure, technically a graph is nothing but a set of vertices and edges
and planarity is a property of a graph
(not of a drawing of said graph)
a face depends on the drawing
calm comet
can you not define a face based on the set?
pale epoch
probably not
scarlet current
if a relation is symmetric then for all a and for all b, if (a,b) is element of R then (b,a) is element of R right?
but then why is the equal relation considered symmetric
isnt the equal relation
for all a and for all b, (a,b) is element of R if and only if (b,a) is element of R
pale epoch
if a relation is symmetric then for all a and for all b, if (a,b) is element of R then (b,a) is element of R right?
right
what's the equal relation?
you mean "regular" equality?
pale epoch
ye
scarlet current
so if a relation such as the equal relation has a biconditional property then it is also symmetric?
because in the definition it only mentions conditional
pale epoch
in the definition of what?
scarlet current
definition of symmetric
pale epoch
i mean $$\forall x, y\colon (x, y)\in R \implies (y, x)\in R$$ is equivalent to $$\forall x, y\colon (x, y)\in R \iff (y, x)\in R$$
vital dewBOT
Lochverstärker:
pale epoch
due to the "for all" you can exchange x and y
cobalt sky
So I have this question: How many ways are there to line up 9 people so all three of the following things are true: <@&286206848099549185>
The answer for this is: 9! - 3 * (2 * 8!) + 3 * (4 * 7!) - 8 * 6!
Can someone explain this to me?
scarlet current
if there is a relation R and there exist a pair (a,b) in R such that a is not equal to b, the relation cannot be antisymmetric right?
solid terrace
I guess so, because antisymmetrical means it (a,b) and (b,a) => a=b right?
scarlet current
yes
solid terrace
if there is a relation R and there exist a pair (a,b) in R such that a is not equal to b, the relation cannot be antisymmetric right?
@scarlet current than you're right
scarlet current
ok thanks!
cobalt sky
is there any specific channel for combinatorics ?
drifting sail
#combinatorial-structures is the closest
scarlet current
@scarlet current than you're right
@solid terrace ah apparantly if there does not exist a,b such that (a,b) and (b,a) are elements in R then they are also antisymmetric. so this would mean that my previous proposition would be false right?
glass condor
No, they very much aren't 🙂
scarlet current
would relation R = {(1,1)}
be reflexive, transitive, and symmetric?
it would not be assymetric and irreflexive right?
it would also be antisymmetric right?
glass condor
it's not antisymmetric.
(1,1) and (1,1) are both in it, hence not antisymmetric.
actually, nevermind, yeah
doesn't apply to the same element.
scarlet current
yeah so the relation is reflexive transitive symmetric and antisymmetric right?
night scroll
does anyone know how to use scheme, the programming language for discrete math?
mystic moss
that's a question?
livid cobalt
@night scroll wouldn't call it the language for discrete mathematics, but do you have a question about it? also, #computing-software is probably the channel for this sort of discussion
stark creek
hi!
i have this recurrence relation im stuck on
i dont know what to do about the squares
$a^2{n+2}-5a^2{n+1}+4a^2_n=0$
vital dewBOT
nomad1c:
stark creek
n>=0 a0=4 a1=13
jolly pulsar
the first one states there exists an n such that for all m, P(m, n)
the second states for all m, there exists an n such that P(m, n)
try plugging in any value and check if theyre true or not for those specific values first if it doesnt come easily
unique herald
I think I see how they are different
The first is stating there is a value of n that will always satisfy the predicate no matter what value of m is plugged in
Whereas, the second one is stating that for every single value of m, there will be atleast one value of n that will satisfy the predicate.
Am I thinking through this correctly?
fair wedge
Yo
unique herald
@jolly pulsar
jolly pulsar
Am I thinking through this correctly?
@unique herald yep, all you need to do is to check for the specified predicate and get a truth value
pliant geyser
Im a bit confused subset only focus on inside the braces of a right?
but then { } is a subset of every set right ......?
steep veldt
karmic nymph
would this be transitive and irreflexive?
er
hm
so its not reflexive
only transitive
right?
gritty crescent
Yes, it seems to be only transitive.
quaint star
Fun exercise to the person who just deleted their question. What is wrong with the following proof? If R is transitive and symmetric and xRy then yRx so xRy and yRx means xRx. Thus R is reflexive.
unreal stump
That's what I was thinking
quaint star
So what's wrong with it?
unreal stump
There may not be a xRy for some x,for any value of y?
quaint star
Yes. We are assuming x is related to some y, but it's possible x isn't related to anything. Then we can't get xRx for that x.
stray reef
the empty relation is vacuously symmetric & transitive
pale epoch
it is on the empty set
gritty crescent
Yeah, I realised it doesn't hold in general.
Hey Loch, if you don't mind I have a question pertaining to group homomorphisms in #help-2 (both abs. algebra and discussion math seem to be occupied). Could you please take a look?
unreal stump
(Idt most people will see the questions chat)
rustic stratus
does anyone know what this hat means
unreal stump
Complement of B
rustic stratus
ty
rustic stratus
is this enough proof for that question?
unique herald
What am I trying to do when I am proving this
ye
But isn't this not true
if the first statement is true, the second statement can be false
rustic stratus
yeah im on that one ig were in the same class LOL
rustic stratus
understanding this stuff in english is normally pretty easy but then finding the right symbols to prove it is always so hard
unique herald
It says that a intersection b complement is empty set
a does not have to be a subset of b
for that to be true
oh wait i see
because complement b is everything not in b
righttt
Btw
could u explain to me the difference between implication and biconditional
rustic stratus
is this not enough details? idk what else to add besides basically repeating the last questions proof
quaint star
Is $\overline{B}$ the complement of B?
vital dewBOT
Lunasong:
sick swallow
lol have u tried thinking
open narwhal
wise dew
hi could someone walk me through the problem in #help-7｜zen1thxyz
🙂
ty
ill be in VC
cosmic jolt
yh please help him
minor dagger
$2^{n^2-n}$
vital dewBOT
Star_:
glass condor
yeah. Arbitrary binary n x n matrix with ones on the diagonal.
minor dagger
yes
steady kernel
What consistent means?
karmic nymph
i think it means true if given the same truth values
but they arnt logically equivalent right
yeah just checking
cuz
someone else was claiming that they are
just needed to check my sanity
steady kernel
how can something with two terms be logically equivalent to something with three
@minor dagger
If R is a contradiction, I think
karmic nymph
aight thank you
so outside of that
The answer to my question is no
right?
@minor dagger
$ (P \wedge Q) \vee \neg (\neg P \vee Q) \equiv P$
vital dewBOT
Yes:
karmic nymph
thats also logically equivalent??
ember obsidian
@karmic nymph yes
karmic nymph
i c
wintry schooner
hey guys how would I find the relation between these two planes
atm I have n1 = (2, 1, -3) and n2 = (2, -1, 3)
but im not sure how to tell if they intersect/parallel etc. i get confused on that part
I think the answer is that it intersects, and it is not parallel and the planes do not coincide aswell
wintry schooner
Sorry
steady kernel
$A := $ Students that see comb $B :=$ Students that see Probability.
$A \cap B$ take both and $A \cup B $ take at least one
$|A \cup B| = |A| + |B| - |A \cap B|$
vital dewBOT
Enigsis:
steady kernel
That's why, if you sum $|A| + |B| $can happen that counts two times people that take both courses, that's why the $-|A \cap B|$ term
steady kernel
$A \cap B$ take both
vital dewBOT
Enigsis:
steady kernel
If a student belongs to that, it have to belong to A and B
That means he takes both
pallid belfry
(P U Q) U R and P U Q
@karmic nymph I am assuming yes they are not equivalent just by looking at them
Because the right side has the universal R whereas the left side doesn't
I am confused as to how that applies to this question though
glass condor
$$n=1:A_1 = {a}. 2^{A_1} = {{a},{}}$$
Then at every step, you can take any subset of $A_{n-1}$ and either take the new element or not - that's where the doubling per new element comes from.
vital dewBOT
ConfusedReptile:
quaint star
He just explained.
sick swallow
do u know induction lol
quaint star
Suppose it's true for all sets with n = k elements. Then you need to show its true for n = k + 1. Let A have k + 1 elements. Then remove one of the elements of A, and call it B. Then B has k elements so it has 2^k subsets. Now for each subset of B, you can either add the removed element or you can not add it. So you get two subsets of A for each subset of B. So there are 2*2^k subsets of A.
stray reef
this is hard to read
fossil minnow
\textbf{Q03.} Let $n$ be a positive integer and let $a_1, \ldots, a_n \in [0,1]$ be real numbers. Show that
%
$$
1 - \sum\limits_{i = 1}^n a_i \leq \prod\limits_{j = 1}^n (1 - a_j).
$$
vital dewBOT
spodamon:
fossil minnow
is that better?
stray reef
yeah now it is
hmm... there is an elegant proof i can think of rn but it uses a concept from probability, which i'm not sure if you're ok with
fossil minnow
is it possible to maybe use induction to solve it?
weary tiger
Hmm, what are you thinking of anyways @stray reef
stray reef
consider a sequence of n biased coins such that the i'th coin has probability a_i of coming up heads independently of the other coins
we toss all these coins once each. let H_i be the event that the i'th coin is heads (and accordingly, let T_i be the complement of H_i, i.e. that the i'th coin comes up tails)
for i = 1, 2, ..., n
consider now the event that at least one of these coins came up heads
i'll call it A
on the one hand, $A$ is the complement of $T_1 \cap T_2 \cap \dots \cap T_n$, and so $$P(A) = 1 - \prod_{i=1}^n (1-a_i)$$
vital dewBOT
Ann:
stray reef
does that make sense so far
weary tiger
Er, sorta, my probability is a bit rusty, but I can appreciate a proof since im just watching from the sidelines. I'm not sure about whoever asked the question tho
fossil minnow
umm yeah but I'm pretty sure we are supposed to use induction to solve this since thats what we are learning in class atm
the proof seems very interesting tho
weary tiger
@fossil minnow have you learned strong induction?
stray reef
i'll give it some thoughts but an induction proof seems really clunky here
fossil minnow
much appreciated 🙂
gritty crescent
Discrete Math textbooks can be a good starting place for elementary aspects of set theory
For more rigorous theory/problems, you could consult any intro to mathematical logic text.
livid cobalt
opal cedar
How would you show that $x^(r-1) = (x-1)(x^(r-1)+...x+1) for any real number x and positive natural number r
ope I didn't do that LaTeX right
opal cedar
I just ended up subbing 3 lol hopefully that's good enough
gritty crescent
Even if the parity of k is even, odd otherwise.
weary tiger
gritty crescent
Correct.
sleek swallow
@fossil minnow
Here
That's the inductive step for you. I'll let you handle the base case on your own.
fossil minnow
Aii thanks man
sleek swallow
You're welcome
weary tiger
@sleek swallow For your inductive proof, would you consider using two base cases for n=1 and n=2
weary tiger
@sleek swallow
\underline{Base Case}: n = 1
\begin{align*}
1 - \sum\limits_{i = 1}^n a_i &\leq \prod\limits_{j = 1}^n (1 - a_j) \[1pt]
1 - \sum\limits_{i = 1}^1 a_i &\leq \prod\limits_{j = 1}^1 (1 - a_j) \[1pt]
1 - a_i &\leq 1 - a_j
\end{align*}
sleek swallow
That last inequality is wrong
The right-hand side is supposed to be $1-a_1$, not just $a_1$.
vital dewBOT
Abhijeet Vats:
weary tiger
Er sorry my bad, a little late here as well
vital dewBOT
SoLongHongKong:
weary tiger
Would it suffice to simply show this in your opinion? I'm relatively new to induction but it seems that it would make more sense to demonstrate n = 1 and n=2 as base cases
sleek swallow
This would suffice. You don't have to show that it holds when n = 2 because it isn't needed later in the proof
But also, your last inequality should be:
$$1-a_1 \leq 1-a_1$$
since you're removing the summation and the product.
vital dewBOT
Abhijeet Vats:
sleek swallow
Other than that, it's fine
weary tiger
Wait why is the RHS $1-a_1, wouldn't it be $1-a_j$ since j was used as the index?
I could be totally wrong lol
vital dewBOT
SoLongHongKong:
sleek swallow
Well, we have that:
$$\prod_{j=1}^{n} (1-a_j) = (1-a_1)(1-a_2) \ldots (1-a_n)$$
So, when $n = 1$, the right-hand side just becomes:
$$1-a_1$$
vital dewBOT
Abhijeet Vats:
sleek swallow
Not a problem at all
weary tiger
I misread what you said
sleek swallow
Get some sleep
karmic falcon
Anyone able to help me with this problem. Understanding it better by chance.
Prove or disprove the following claims.
Let R, S, T, U ⊆ Z ... Z being integers.
(R-S)-(T-U) = (R-T)-(S-U)
slimvesus:
limber elm
Hey would anyone be able to help me with a question about the pumping lemma?
stoic owl
Anyone know an infinite sum or closed form expression which takes indices i, j >= 0 as arguments and returns the value of the ith row jth column of the infinite matrix defined by the non-negative integers arranged in colexographic order? (ie, the 2d array of this sequence https://oeis.org/A195664)
karmic falcon
Did you mean to put the element symbol
@weary tiger Yes that. Any ideas?
karmic falcon
Try using the distributive property
@weary tiger The - is supposed to be / .. Difference of sets btw.
weary tiger
last sigil
try literally drawing out the interval
weary tiger
i did
last sigil
so what are you stuck on specifically?
weary tiger
understanding how this relates to the pigeon hole principle
last sigil
Hint: ||Consider dividing up the interval into 6 equal part. What are the sizes of these subintervals?||
last sigil
You want to apply pigeonhole principle
A more visual way to see this problem is that you have an interval of length pi
You want to place 7 points on this line
Prove that the distance between 2 points is less than pi/6
Why did you consider dividing into 7?
weary tiger
i included 0 too
last sigil
Can you restate pigeonhole principle to make sure I understand you know what it is?
wdym included 0
weary tiger
if there are k+1 objects and k boxes, then there is at least 1 box with 2 or more objects
last sigil
correct
weary tiger
yeah like i'm just not seeing how this relates to pigeon hole lol
so i can't relate to it
last sigil
what are our objects in this problem?
The first step when applying pigeonhole is to identify your objects and boxes
weary tiger
oh so the objects could be the a1 , a2 .... a7
last sigil
correct
weary tiger
so then we need 7-1 boxes
last sigil
our 7 points are our objects
last sigil
yes and no
a more natural way to consider why we divide the interval into 6 parts is to look at what we want to prove
0 < a_i - a_j < pi/6
The total length of the interval is pi, and the bound we want to establish is pi/6
weary tiger
ok
last sigil
are you sure
weary tiger
no i am just saying ok to that ^ but i still don't really get it
last sigil
don't get where we are going with this information?
weary tiger
yeah
weary tiger
ok
we have 7 objects: a1, a2, a3.... a7
we want to find two distinct indices that are in the interval 0<= a_i - a_j <= 0
that's all i get
last sigil
we now divide the interval [-pi/2, pi/2] into 6 subintervals of equal size
weary tiger
can you clarify why again?
last sigil
can you clarify why again?
I will ignore this question for now and explain at the end; it makes more sense then
If we place our 7 points onto this interval, what can we say about the number of points in at least 1 of the subintervals?
remember we have 7 points and 6 subintervals
weary tiger
there are two distinct values a_i and a_j that is in the same sub interval
weary tiger
yup
last sigil
Do you see where to go from here?
weary tiger
uhh not really
last sigil
What is the size of each subinterval? Now, what can we say about the distance between the 2 points in the same subinterval?
weary tiger
the size of each subinterval is pi/6
the distance would be 0?
weary tiger
i'm not sure
does the distance between the 2 points have to be anywhere betwen 0 and pi/6?
i just drew it out and i think i'm going to go with the above message ^
last sigil
@weary tiger yeah sorry had to leave for a sec
weary tiger
np
last sigil
yes the distance between the 2 points in the subinterval must be between 0 and pi/6
it is 0 when the 2 points are the same, and pi/6 when they are the "endpoints" of the subinterval
do you see now the entire proof?
We used pigeonhole principle to place our points in the subintervals to guarantee at least 2 points were in the same one
These 2 points can be your a_i and a_j because the distance between them in the subinterval is bounded between 0 and pi/6 (length of the subintervals )
Now, do you see why we picked 6 subintervals, instead of say 9 or 2?
last sigil
Please attempt to write out your proof for 5
weary tiger
lol
last sigil
I don't mean to be snarky
you cannot do it with 5 but you should try to in order to see why you can't
weary tiger
yeah lol
last sigil
how would your proof work if you divided into 5 subintervals rather than 6?
weary tiger
yeah it wouldn't work out
last sigil
why does it fail?
weary tiger
I mean the intervals would be a very weird number
last sigil
uhhh not exactly; the real reason why is because your bound on the distance between the 2 points would be between [0, pi/5)
pi/5 > pi/6, so you have not proved what the problem wanted
weary tiger
hmm truee
last sigil
Ok, I need to leave now
last sigil
To summarize, figuring out your boxes and objects and then how to apply pigeonhole to a problem is 80% of the battle
You see this much more easily with experience and practice with many different types of problems
Here is a nice problem to practice; similar to the one we just solved
Consider a unit square (1 x 1). Place 5 points in the square. Prove the distance between 2 of the points is at most sqrt(2)/2
weary tiger
mystic moss
this one is almost exactly like the previous one
@weary tiger did you read the hint?
weary tiger
yes
mystic moss
this time your points can lie along the entirety of the line x=1
which can seem impossible to break into groups in order to use pigeonhole, but the hint tells us that we can do it using angles from the origin
weary tiger
@mystic moss yeah just no idea how to start
cobalt sky
so my answers are for a) 9! * 8!
mystic moss
(on x=1)
cobalt sky
b) 9! * 9!
mystic moss
connect each point to the origin, and look at the resulting angles
finally, consider what the proposition is saying about those angles. you'll be able to use pigeonhole from there
weary tiger
how do i know that it's between 0 and 1/sqrt(3)
mystic moss
what exactly
weary tiger
like what will drawing help me for?
mystic moss
it'll help you visualize the hint and see where the grouping comes in
weary tiger
i dont get it
mystic moss
did you draw it?
copper ore
ya
weary tiger
copper ore
like that?
mystic moss
yes, and note that they can also be negative
mystic moss
what is the tan of that angle?
mystic moss
use the hint
mystic moss
well first consider that we can find the tan of the angle between each point and the x-axis
what would that be for, say, a1?
weary tiger
tan(p_1)
mystic moss
what is p?
weary tiger
it says let p_i be the point with coodinates (1,a_i)
mystic moss
okay, but we can calculate the tan of the angle directly in terms of a1 here
weary tiger
tan-1(a2)
mystic moss
not the angle, the tan itself
weary tiger
tan(a2)
mystic moss
uhh not quite. perhaps draw a right triangle for that
mystic moss
yeah exactly
so this holds similarly for all ai
consider the angle between p1 and p2. what is the tan of that?
weary tiger
uh like what do you mean exaclty?
mystic moss
like there's a line from the origin to p1 and one from the origin to p2
weary tiger
ya
weary tiger
would you do (p1+p2)/2
mystic moss
not quite, here is specifically where you can use the hint.
look at the angles you found the tans of before and see how they relate to the angle between the two lines
mystic moss
hm look at the angles for p1 and p2 specifically
weary tiger
ok
mystic moss
i gtg for now though. gl with this problem! after finding the tan of the angle in between, relate this to the bound you were given in the question. what's the largest angle you could possibly have for the inequality to hold? use this for your pigeonhole.
weary tiger
thank you for the help! bye
rancid garden
Having trouble understanding mathematical induction on sum of series
steady kernel
Which is your problem? Let me see
steady kernel
Sum $\frac{1}{[2(n+1)-1][2(n+1)+1]}$ to both sides
vital dewBOT
Enigsis:
steady kernel
To do the inductive step
sour brook
hi all, i have a question about Venn diagrams. When is it necessary to draw the rectangle that represents the universal set U, and when can we leave it out and just draw the circle?
minor dagger
you should always try to include it since all sets are subsets of the universal set
sour brook
ok, so i have this question from a textbook
Use a Venn diagram to illustrate the set of all months of the year whose names do not contain the letter R in the set of all months of the year.
and i drew a circle in a rectangle, with {May, June, July, August} in the circle and the remaining months outside of the circle, but in the rectangle
minor dagger
yeah for those kinds of problems you could just do two circles
one inside of the other
the inner one has the months that dont contain R
the outer ring contains the subset of months that dont contain r and the months that do
sour brook
i see is that because the question says "in the set of all months of the year"?
minor dagger
yeah
sour brook
thank you! @minor dagger
minor dagger
either way i suppose you are considering the set of all months the universal set for this case
sour brook
you're a star!
sour brook
how did you draw the diagram so quickly?
minor dagger
i am speed
steady kernel
hi all, i have a question about Venn diagrams. When is it necessary to draw the rectangle that represents the universal set U, and when can we leave it out and just draw the circle?
@sour brook
I think you can leave it out when you aren't doing complement operations
minor dagger
i like to include it if im considering a numerical set usually
shell jewel
vital dewBOT
moar55:
cursive lily
stray reef
well do you think it does or do you think it doesn't
burnt herald
but i dont know how to begin the proving
wild flame
Figured out my problem.
stray reef
@burnt herald you didn't answer my question
burnt herald
@burnt herald you didn't answer my question
@stray reef it doesn't
but i'm not confident
stray reef
then try to find a counterexample
burnt herald
then try to find a counterexample
@stray reef am i allowed to define my own sets?
stray reef
ofc you are, how else would you even construct a CE
burnt herald
sorry
i meant, how do i know if I'm doing CE or not?
do I try to disprove it? if it doesn't mean it's true?
like, i know because i defined the membership table and found out that it's false
stray reef
a counterexample is a counterexample
you first say to yourself "ok i think this claim is false, now im gonna try and make a counterexample to it"
in your case a CE will consist of four sets A1, A2, B1, B2 for which the equality fails
burnt herald
ah
Okay so if i define a set:
A1= {1} A2={2} B1 ={b} B2= {c}
the LHS will be { (1,b) , (2,b), (1,c) ,(2,c)}
which is not equal to RHS
hence False
is that a correct way?
stray reef
i mean you can just say "equality here is just <previous exercise> with the sets relabeled so no. refer to the solution of <previous exercise> for a counterexample"
burnt herald
ah
btw why in this picture, given the example values, it does not hold?
isn't (0,0) , (1,1) a subset of the RHS {(0,0), (0,1), (1,0), (1,1)}?
burnt herald
what am i understanding wrongly?
{(0,0) , (1,1)} every element is also an element of {(0,0), (0,1), (1,0), (1,1)}
stray reef
yes
the question says "prove (...) ⊆ (...)"
then asks "is it also true that (...) = (...)"
and the answer is no
burnt herald
then asks "is it also true that (...) = (...)"
@stray reef sorry is this derived or stated?
oh wait.. it's from "does the equality hold"...
omg
i did not see that, thank you
bitter moss
Ay i love discrete math
-said no one ever
wintry schooner
lol
@bitter moss do you know how I could solve my problem, im trying to show that this relation is an equivalence relation
already proved its reflexive and symmetric
unreal stump
Use definition of transitive
wintry schooner
but not sure how to show that its transitive
unreal stump
Let both 2x+y and 2y+z be divisible by 3,show 2x+z is divisible by 3
wintry schooner
hmmmm
if 2x+y exists and 2y+z exists and they're both divisble by 3
then 2x+z is also an element of the set?
not sure
unreal stump
And why should that be?
wintry schooner
i think its because of this rule
((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R
actually no i might be wrong there
gritty crescent
That's what you need to show
((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R
This is the condition for R to be transitive
wintry schooner
yeah
but im a tad bit confused on how I could actually show the final part
I have that 2x+y and 2y + z are mulitples of 3
gritty crescent
(x,y) in R and (y,z) in R means 2x+y is divisible by 3 and 2y+z is divisible by 3. From these two, you should be able to deduce that 2x+z is also divisible by 3.
Correct.
wintry schooner
yeah, so I could just state basically that....therefore, 2x + z is also a multiple of 3?
right?
hence (x, z) is an element of R
or am i missing a step in this?
OR would I say that therefore 2x+z = (2x+y) and (2y+z) are also multiples of 3 and hence (x, z) is an element of R
gritty crescent
Wouldn't work like that. You kinda have to take the given information and use that to deduce that (x,z) is indeed in R.
Something like maybe 2x+y is a multiple of 3 therefore 2x+y=3m for some integer m. Similarly, 2y+z=3n for some integer n.
Are you sure this relation is transitive though?
wintry schooner
Yeah one of my exercises says to show that R is an equivalence relation and I already showed that its symmetric and reflexive
gritty crescent
Hmmm...let's see where we can get from here then.
wintry schooner
hahah yeah
mystic moss
psst: what's the difference between (2x+y) + (2y+z) and 2x + z
wintry schooner
difference?
mystic moss
you know the first one is a multiple of 3. you want that the second one is a multiple of 3. therefore the difference must be a multiple of 3.
wintry schooner
hmmm so I have to show 2y + z = 3n for some integer n?
mystic moss
i meant that the first one is: (2x+y) + (2y+z) and the second one is: 2x + z
wintry schooner
yeah but thats the thing im not sure how to show that 2x + z is a multiple of 3
mystic moss
the difference must be a multiple of 3
wintry schooner
so ((2x+y) + (2y+z)) - (2x + z) = 3k for some integer k?
am I on the right path?
mystic moss
yeah
wintry schooner
so is there another step missing?
mystic moss
just simplify the expression
wintry schooner
oh okay
so ((2x+y) + (2y+z)) - (2x + z) = 3k for some integer k?
but however this is the final answer right?
before simplifying
mystic moss
idk what you mean by "final answer" because it's a proof, but yeah after you show that you'll be set
wintry schooner
yeah thats what I mean haha
sorry im new to discrete maths but I appreciate the help guys!
also ty ted
and drake
weary tiger
Madeleine is it possible if we can continue from yesterday 😅
mystic moss
sure thing, where are you at now?
weary tiger
i'm at the same spot
mystic moss
reiterate to me what we've done
weary tiger
ok
so we drew a cartesian plane
and plotted 7 points at x = 1
we found the tan of p1 = (1,a_1) and p2 = (1,a_2) right?
mystic moss
right. call the angles from the origin to each of those points b_1 and b_2
now we want the tan of the angle between the lines going to p_1 and p_2
call that angle b
relate b, b_1, and b_2
weary tiger
are we using b instead of p?
mystic moss
b is the name of the angle, not the point itself
weary tiger
oh ok
so if we want the tan of the angle between the lines of p1 and p2, we can use that tan(a-b) formula right?
weary tiger
oh ok. So where alpha = a1 and beta = a2?
mystic moss
*b1 and b2, because we're talking about their angles
weary tiger
oh right
weary tiger
so b=b_1-b_2
don't we have to divide by (1+tan(b_1)(tan(b_2)) also?
mystic moss
no that's for tan(b) not b itself. b is the angle, tan(b) is what we're calculating with the hint
i'll say it explicitly ig
tan(b) = tan(b1 - b2) = (tan(b_1) - tan(b_2))/(1+tan(b_1)(tan(b_2))
now you can substitute what you got for tan(b_1) and tan(b_2)
weary tiger
for tan(b_1) we got p1 and tan(b_2) we got p2?
mystic moss
yup
weary tiger
tan(b) = tan(b1 - b2) = (a_1 - a_2)/(1+(a_1)(a_2))
mystic moss
exactly, does that look familiar?
weary tiger
ya
thats in the range
right
of 0<= x <=1/sqrt(3)
where x is tan(b1 - b2) = (a_1 - a_2)/(1+(a_1)(a_2))
mystic moss
right, the problem says that there must be one such pair (i, j) for which that is true
note that 1/sqrt(3) is tan(pi/6)
and so it's basically saying that at least one angle b must be less than pi/6, or 30 degrees
split up the line x=1 into 6 groups by drawing radial lines from the y-axis that are 30 degrees apart from each other. like a fan, almost. do you get the visualization, or is this too vague?
weary tiger
i don't get that
mystic moss
let's see if i can draw it
weary tiger
ok thank you
weary tiger
ya
mystic moss
pigeonhole on those 6 groups
weary tiger
so each of these are 30 degreess?
mystic moss
yeah
weary tiger
ok thank you
vast jungle
Hello, I'm pretty green on discrete math. Just asking how would this be read
{{∅}} ∈ {∅,{∅,{∅}}}
Thank you
brave lava
<@&286206848099549185>
glass condor
check the definitions of being 1-1 and onto
then see if this functions fullfills them.
wintry schooner
right okay thanks
okay i read up the definitions but i still dont know how to apply it to the function in my question
from my understanding of the definition i believe the function is not 1-1, is that right?
drifting sail
Yes that's right. Note for instance that f(1,1)=f(-1,1)=1.