#discrete-math
weary tiger
copper ore
o
anyways i have another question
Prove that 𝑥+1/(4𝑥)≥1 for all real numbers 𝑥>0.
If you wish you may use calculus or the quadratic formula to demonstrate the existence of a specific minimum value, should you need to do so.
how would you do it by induction? @weary tiger
for that earlier one
weary tiger
that's also induction right now
copper ore
lol
weary tiger
the earlier one, just choose a random real for x, say 0
then your inductive hypothesis is that the equation stands for all reals
then assume it works for all numbers n
prove that the statement is true for n + k where k is any real number
your base case would be that when x = 0
weary tiger
for the second one
it's asking you to just set the base case at x = 1 and just do induction
in the positive direction
copper ore
okay i just learnt induction so i think i have to review notes
sour arrow
So "assuming the equation holds for all real numbers" can't be part of the hypothesis, since that's what we're trying to prove
sour arrow
There's only one value when
x + 1/4x = 1
Solving it as a quadratic, that's x = 1/2
Also worth noting, x + 1/4x is continuous everywhere except x = 0
glad oriole
umm no
weary tiger
try for x + k
azure lichen
induction on the reals requires that you have the statement proven on a whole interval
sour arrow
So, we sub in a few points to check values. Let f(x) = x + 1/4x
f(1/4) = 5/4
f(2) = 17/8
And we're done
azure lichen
like on [0,1) or so
weary tiger
you can try k for any real
if you show that your step is any real
you can do induction
any positive real.
azure lichen
that doesn’t sound like induction
that’s more like “doing it for all numbers at once”
glad oriole
actaully if you know that x+1/x >= 2 for all positive reals then x+1/(4x)=1/2 * (2x+1/(2x))>=1/2 * 2=1
x+1/x>= 2 can be proven by examining a quadratic
weary tiger
@azure lichen that's what I was taught as "induction on reals" 
copper ore
if i did proof by cases, what cases would i need?
wary salmon
copper ore
@glad oriole could you help me with the quadratic method? i'm doing that right now and my teacher gave a hint to use that too
glad oriole
yeah all right
copper ore
i have the algebra down but i'm doing proof by cases so i just need help with cases
glad oriole
okay what cases you need help with?
copper ore
yea
glad oriole
oh wait no it isnt
copper ore
so i need help with what cases i need to use to prove that 𝑥+1/4𝑥≥1 when x>0 for all real numbers
how
glad oriole
you need to multiply both sides by 4x
copper ore
yeah i did
glad oriole
holy shit wait you did
copper ore
lol
glad oriole
omg im so sorry
copper ore
it's fine
my pic is p hard to read 😛
cause of that bigg shadow of my phone and hand
copper ore
i tried doing proof by induction but then it's all real numbers so it wouldn't be possible
i don't have to do it by cases i could use another proof method.
glad oriole
yeah a proof by examining cases wouldn't be very useful here
copper ore
hmm okay
glad oriole
cuz then you'd basically have to prove the same statement but you'd have to do it more than once
one for each of the cases
glad oriole
which two cases are you thinking of?
glad oriole
x>1/2
glad oriole
becuase 1/2 is the extrema of the parabola
glad oriole
see the thing about splitting into cases like that
is it doesn't make the problem easier
you just have to prove the same thing twice
glad oriole
ok we'll try that then
copper ore
were you thinking of any other proof methods though?
glad oriole
yeah i have a couple
kaynex already said one
and i posted the other idea up above
if you still wanna do it by cases then ill help with that
copper ore
Proof by Cases
Vacuous Proof
Trivial Proof
direct Proof
indirect Proof
Proof by Contradiction
Equivalence Proofs
proof by induction
Existence proofs
Constructive Existence Proofs
Non-Constructive Existence Proofs
these are the proofs i can use.
would proof by cases be valid proof to use?
if so, could we do that i guess?
copper ore
arghh
this is hard to decide
so for direct proof its like an implication right
if we had P --> Q
we would assume that P is true
but what would P be in this case?
late gust
uh
not to jump in on a conversation i'm not a part of
but the statement to prove is just x + 1/4x >= 1 for any positive real right?
we can do cases
for x = 1 or above
we'll have x + some positive number, so we're fine
copper ore
yup, it's for all real numbers 𝑥>0.
glad oriole
but how would that be easier than direct
and you can make my statement imply x+1/4x >= 1
simply substitute x = 2x
and multiply both sides of the inqueliaty by 1/2
late gust
oh so the discussion isnt about how to prove, its which one is best?
glad oriole
and you have the statement
copper ore
yeah it is to prove
so i was doing cases first
but then i guess we're doing direct now
i don't care which one though lol
glad oriole
i mean if you want to prove it by cases then ill help but its just that direct is easier
late gust
direct is pretty easy
cases is easy too though
it's not super difficult as proofs go, but i guess if we want to be efficient, direct may be better
although i'm not sure
glad oriole
^
glad oriole
copper ore
lol
wait so for cases though, you're allowed to have only 1 case?
or is it 2 minimum
tbh though guys
can i keep my math i used to cases
in my direct?
late gust
idk how you did cases
but there's no limit
as long as your cases cover everything
the union of all your cases should end up with what you had to prove over again
in this case, the positive reals
copper ore
this is what i did for cases
but i was stuck on the first case lol
that's where this whole convo started
late gust
do that in reverse
direct proof done
qed
the square thingy
wtv
start with (x-1/2)(x-1/2) >= 0
because thats just a square
copper ore
ok
late gust
and all squares are 0 or above
then do everything you did again
you end up with the statement
copper ore
which statement
late gust
the original statement you had to prove
mind if i ask what class you're doing this proof for?
copper ore
discrete math
i don't have a lot of experience with direct proof
i think i've only done 1 so far
late gust
do you have a lot of experience with proof in general?
copper ore
not really
like we just started learning this 1 week ago
but my course is p fast
so yeah
we started learning proofs one week ago but the other concepts that come with proofs i know p well
@late gust how would the case look?
if i were to do cases
late gust
im thinking right now, i thought i had one that would work, but i'm not too sure anymore
here's what i have so far
if x >= 1
the x part is already >=1, the whole thing is fulfilled
if x <= 1/4
the 1/4x part would be >=1, the whole thing is fulfilled
now we just need to find out for 1/4<x<1
copper ore
x is suppoed to be >0
late gust
?
copper ore
why did you do 1/4
late gust
because those cases were very easy to prove?
copper ore
how would you do that algebraically?
if x >= 1
the x part is already >=1, the whole thing is fulfilled
like this part
late gust
If x>=1, then x + 1/4x >= 1
Like
Because everything is positive
i mean
If 0<x<=1/4, then 1/4x >= 1, then x + 1/4x >= 1
late gust
Here's the least convoluted way I could think of doing the last bit
If 1/4<x<1, x+1/4x = (4x^2 + 1)/4x needs to be greater than or equal to 1. Or, 4x^2 + 1 >= 4x
1>= 4x - 4x^2
1> = 4(x-x^2)
Actually yes it does help
uh
did you see that part or do i need to type it again?
late gust
alright
copper ore
i didn't get to read it
late gust
so basically, we want to maximise x - x^2
because its a quadratic with a negative x^2 term, there's only one critical point and its the maxima
using calculus, we find the critical point by doing the derivative and setting it to 0
we get x = 1/2, which is in the domain we set for ourselves for this case
that means that the maximum value of x - x^2 = 1/2 - 1/4 = 1/4
or 1 >= 4*1/4 = 1
i guess tedchnically we'd need to work backwards
from here
but that's the gist of it
yeah so direct proof was much better
late gust
because we want to show 1 is always larger than 4(x-x^2)
and if we show that its larger than that at its maximum
well then we've shown it for all haven't we
late gust
¯_(ツ)_/¯
late gust
he's still online
copper ore
that means that there can't be anything lower
in that interval
do you know how the graph of this thing looks?
so since 1/2 is the lowest point in that interval
copper ore
ya but shouldn't we work with the graph
late gust
says who? the math police?
copper ore
no lol
late gust
proof by cases is a tool
its up to to prover to choose which cases
if they're clever, there are fewer cases
if they're not, they can have a bunch of cases and deal with each one individually
late gust
then use those cases
late gust
why'd you use those cases?
copper ore
wasn't your (0,1/4)?
late gust
yes
copper ore
i used 1/2 cause the x value of the minimum value is 1/2
late gust
and how did you prove that it was the minimum?
copper ore
i didn't prove it.
i just did it algebraically
that pic i sent
earlier
shows it
late gust
if you've shown it, then you've proved it
i mean the minimum output of a squared function on the reals is going to be 0
so you've proved it there
then, you don't need casework
azure lichen
that is a proof techique
copper ore
how
azure lichen
everything is a proof technique
there is no fixed set of proof techniques
if you have a set of conditions, and you show that from this, another thing follows, that’s a proof
copper ore
but i listed the ones im supposed to use earlier
ok im supposed to use one of these
late gust
i mean, that's a trivial proof really
azure lichen
(I’m guessing, I don’t know half of these names)
late gust
squares are nonnegative?
copper ore
directly doesn't mean directly lol
azure lichen
I mean if it’s the opposite of an indirect proof then it’s just not one by contradiction
since an indirect proof is one by contradiction
slash by making a false assumption
azure lichen
badly, is my guess
late gust
Ok, look. You've been given a statement to prove. You've also been given an (unnecessarily verbose) list of proof methods to use. That doesn't mean you aren't allowed to use algebra - that's like being told you can use a wrench, but you can't use the garage. We've used "direct proof" already to prove the statement once. If you still want to try by cases (which is good - practicing more for proof is always the right way to go), then you need to understand the principle behind proof by casework.
When you want to do casework, there's no set cases that you need to use. There's no book with a list of every trivial little proof listing exactly what cases you can and can't use.
The idea behind casework is to divide and conquer - see which parts of the proof you can do very easily and then do each of those parts until you've eventually done the whole proof.
So, take your original problem, and just think about it to yourself - if we could change the domain (which is currently all nonnegative reals), how could we change it to make the problem super easy?
azure lichen
it also usually combines with other proof methods
you might see that you have to do x=0 separately or sth
late gust
yeah, it's not like if you're using the hammer, you can't touch the wrench
azure lichen
and then perhaps you need a contradiction for x<0 but can do it constructively for x>0 or what not
(not in this example)
late gust
he doesn't really need the contradiction, because the statement is only prove a for b, not prove a iff b
azure lichen
(not in this example)
late gust
yeah my bad, sent that right after i saw that
azure lichen
I didn’t even really look at the example, I’m just making general statements
copper ore
badly, is my guess @azure lichen that was mean
azure lichen
I will happily be mean to bad education systems
azure lichen
it has nothing to do with you
you’re being taught badly, is what I assume
not that you are bad
copper ore
oh true.
azure lichen
those are entirely different things
copper ore
true yeah
late gust
it's not your fault, but generally, math education can get very trash
have you made any progress on the proof?
copper ore
i guess so
nah bro
like so the thing is
i understand your analogy of the definition of a proof ( the wrench one)
but
i kinda have to do it this way
my teacher makes it like this
late gust
what do you mean he makes it like this? do you have an example of how he does proofs?
he may be just being more rigorous, but that doesn't mean he's going to stop you from using algebra lol
copper ore
oh no i can use algebra.
late gust
Then the earlier point was fine - you can justify your use of 1/2 there because it's the minimum.
From there, the proof is easy - because 1/2 gives the smallest value of that expression, prove that it fulfills the statement.
Then, if 1/2 (which gives the smallest output) works, then everything else must work, because they're all bigger than the minimum.
You don't even need casework. If you need to keep your teacher happy, call it direct proof.
late gust
Is this a university course? If so, you might want to have a serious talk with your teacher if you're finding his teaching difficult to understand, or even worse case switch classes or something.
late gust
If you're in university, your education is the priority, so do what you need to, talk to whoever, as long as it gets you better math teaching.
late gust
I'd assume your teachers and administrators would be the most help.
late gust
Is your major math, or cs, or something else math heavy?
copper ore
cs
because 1/2 gives the smallest value of that expression, prove that it fulfills the statement. oh im having trouble doing this
late gust
one sec, i gtg do something, i'll be back
dense thicket
It has to be right?
Also are these true?
< meaning just a standard relation of which ones bigger
lex order has to be isomorphic from what Im thinking
product one not since its not a chain?
analog sonnet
First one seems true, but you'd have to explain more about your second question
dense thicket
Is function f(x, y) = (x+y, x-y) a surjection, injection?
X, y are reals, f: RxR - > RxR
Also: Is set RxR \ QxQ just R\QxR\Q?
viral stump
yes, yes, no
notice that f is linear
the result follows
for the other one, consider (pi, 3)
azure lichen
the element (π,1) is found in (ℝ×ℝ) \ (ℚ×ℚ) but not in (ℝ \ ℚ) ×(ℝ \ ℚ)
echo lintel
idk if this goes here, the class is called math foundations of computer science but i could use guidance
hearty crane
slow socket
how do i make the matrix A[ i, j ] = ij
analog sonnet
Make...?
opal crescent
modest zealot
wait is the negation of biconditional equivalent to exclusive or...
modest zealot
wait how come?
crystal oar
if by biconditional you mean (A implies B) and (B implies A) then yes that is equal to not(A xor B)
modest zealot
ah ok
dense thicket
REact cat emohji if you like set theory
dense thicket
No.
slow socket
i got the the relation on S = {0, 1, 2, 3} and they give me (m,n) element R2 if m + n <= 4
why is this not reflexive or symmetric
azure lichen
those are so few elements, just draw a 4x4 grid and label all pairs in the relation
reflexive means the "diagonal" is in the relation, symmetric exactly that
(across that diagonal)
slow socket
wat about the condition though? m + n <= 4
was m+ n sorry
i've never done 4x4 grid for these types of problems
can u explain wat u mean
dire folio
Hello, I might be taking discrete math next semester and I was wondering what it's briefly about?
dire folio
Europe
pale epoch
then it often involves some combinatorics, maybe ramsey theory, generating functions
and the biggest part is often graph theory
dire folio
Oh, what career aspects are they usually applied in?
pale epoch
maybe number theory, depending if this is a separate class at your uni
graph theory especially is prominently used in computer science
pale epoch
Hm, I don't know maybe
I know it's used in network design
and general business planning
many quite general problems that are often solved using linear programming can be solved more efficiently in a graph theoretic setting
besides, graph theory is a big subject where many NP-hard problems arise
and solving them faster in special cases is what many computer scientists care about
for example the traveling salesman problem
dire folio
Interesting
pale epoch
i know many graph theorists who work in public transportation as well
for example planning train stuff
street network (and also digital networks) are modelled using graphs
dire folio
For optimizing network flow right?
pale epoch
yeah
or dunno, google maps is finding shortest paths in a graph
recently there is talk to use certain graph theory problem for cryptography
especially post-quantum cryptography
dire folio
Ah, I see, thanks a lot for the information.
static surge
I'm currently learning the pumping lemma, and there is something I'm misunderstanding. How can the 2p > p inequality hold true?
crystal oar
2p is larger than p?
static surge
If I understand the 2p correctly, it comes from the a^p b^p, since there are two characters, each repeated pumping length of time, but the 2p > p throws me off
Oh wait, I am not sure what I was thinking, forget I said anything XD
For some reason, my brain was reading that as 2p < p even though I clearly wrote 2p > p
crystal oar
slate sleet
static surge
What problems are you having with the questions?
acoustic valve
How would I go about proving this?
I'm very stuck, I'm not sure what direction to go in.
glad oriole
if n is even then n^2-1 is odd so for even n, n^2-1 will not be in the intersection
(2k is the set of all even numbers)
what would happen if n is odd? that is if n is of the form 2a+1 for a an integer?
acoustic valve
thanks
my second question
would you eat stuart little alive for ten million dollars
glad oriole
yes
scarlet mantle
hello, i am looking for a site or youtube channel that covers my course ; his name is mathematics for computer science
we talk about sets , demonstrations , boolean algebra etc
if somebody could help me out would be nice, thanks !
viral stump
mit ocw
math for cs 6.042
weary tiger
Could some one help me understand this? I got the right answer but don't really understand how.
viral stump
draw it
crystal bough
(a,b)belongs to relation R only if a^2 + b^2 = a + b
to check reflexive I found (a,a) but it's only true for a = 1, then is it reflexive?
Relation is defined on positive integers
opal crescent
it's not reflexive then (the domain is the positive integers, not {1})
aRa has to be true for every a in the domain for the relation to be reflexive
weary tiger
<@&286206848099549185>
sage island
t!wiki multinomial theorem
uncut groveBOT
weary tiger
for this question it was told that i use bional theorem
sage island
well then it's just a two step application
azure lichen
the k is there to give you all possible terms. you've already manually set it to 3
because you've noticed you only need that
get rid of the summation
well, except there's an issue with setting it to 3
because this gives you x^7
when you wanted x^3
quaint river
I can help with the group part but i dont understand what else its asking..
so anyways to show something is a group you have to show that there exists an identity, inverse, its associative, and its closed
the identity is simply $ f^0$ in this case
vital dewBOT
Victoria:
quaint river
and then the inverses of $f^n$ if $ n \neq 0 $ are just $f^{4-n}$
vital dewBOT
Victoria:
bright gulch
Yes I got it
The tough part is
I have to prove that this function is isomorphic with Z4,+4
Which is Z from 0 to 3 addition modulo 4
quaint river
By definition any cyclic group of order n is isomprhic to z_n
in this case, it is cyclic since your generator is just f^1
if you need to prove it, just map the generators
i.e your generator in this case is f, define $\phi$ as your isomorphism, and $\phi(f^1) = 1, \phi(f^2) = 2.. etc $
bright gulch
Wait isn't isomorphic a^n
vital dewBOT
Victoria:
quaint river
i dont really understand that question, a generator is a element say $a$ of a group G such that the set $ {a^n | n \in \mathbb{Z}} = G$
vital dewBOT
Victoria:
quaint river
but when we define powers in this case we define it to be the group operation, i.e $(f^1)^2 = f^1 \circ f^1$
vital dewBOT
Victoria:
bright gulch
It works that way ?
quaint river
thats how we define a group generated by an element yes
quaint river
Well do you know what a isomorphism is
quaint river
Just define your isomorphism to be this function
and verify that it does indeed
satisfy those properties
bright gulch
The problem I was encountering was how do I write f(a ° b) as f(a) + f(b)/4
Like we have to prove these are equal
vital dewBOT
Victoria:
quaint river
its simply $f^{n+m\ mod\ 4} $ right
vital dewBOT
Victoria:
quaint river
then if we use the same f^n, ^m for the other side, we get
$\phi (f^n) + \phi(f^m)\ mod\ 4 = n + m$ mod 4
vital dewBOT
Victoria:
quaint river
by definition of phi
bright gulch
But will they have the same value
quaint river
yes they will they're the same expression
bright gulch
Sorry if I sound dumb, discrete is a subject I have to study being CSE in first year and it's really a slow death for me
vital dewBOT
quaint river
,rotate 180
vital dewBOT
quaint river
@bright gulch
you can prove onto and one to one yourself I don't think those are hard
bright gulch
@quaint river thanks a lot
@quaint river one last query we don't have any relations between f2 and f3
What do we do for that
quaint river
Wdym?
quaint river
No look
bright gulch
F^(n+m)%4
quaint river
F^2 circle f^2 can be split into f^1s
bright gulch
So f3°f3 would be f2?
quaint river
Yes
bright gulch
Oh yeah it is
Pretty amazing
I wish my teacher taught me this way then I wouldn't study this for the heck of it
Thanks a lot , respect ++
slow socket
why does
5MOD6 = 5 and
4MOD6 = 4 and then
5MOD6 + 4MOD6 = 3
weary tiger
@slow socket what is the remainder of the Euclidean division of (5+4) by 6?
quaint river
Because a mod b is just the remainder when a is divided by b
slow socket
3
weary tiger
you answered yourself 😄
weary tiger
yep
slow socket
cool, thanks
weary tiger
you welcome 😃
magic parcel
Im fairly new to this type of math, and was wondering if anyone could tell me if im doing this right. So my task is, given that an agency that books hotel rooms books 20% of their clients to hotel A, 50% to hotel B, and 30% to hotel C, wherein 5% of the rooms in hotel A have faulty plumbing, 4% in hotel B have faulty plumbing and 8% in hotel C, what is the probability that a guest will recieve a room with faulty plumbing? Would it be correct to just add all the probabilities of faulty plumbing, or is that wrong?
bitter latch
this should be on #probability-statistics
you sum up all the probabilities of getting room with faulty plumbing on hotel A, B, and C
slow socket
Can someone guide im the right direction on how to do this
craggy gale
Do you know the definition of what is an equivalence relation?
slow socket
ya, it has to be reflexive, symmetric, and transitive
craggy gale
Well then you just have to check if the given relation satisfies these properties
for example, for all n in N, n²-n² is very well a multiple of 3, so for all n in N you do have n~n, which means ~ is reflexive
slow socket
so like n^2 - m^2 is a multiple of 3, ~ is symmetric
pale epoch
To show symmetry you have to show that if n^2-m^2 is a multiple of 3, then m^2-n^2 is a multiple of 3 as well
slow socket
it is a multiple of 3 either way u do it
pale epoch
What do you mean?
slow socket
why k in Z?
dense thicket
n might be smaller than m
dense thicket
yeyeye exactly
slow socket
i got m^2 - n^2 = -3k
dense thicket
yeah, which makes is symmetric, right?
slow socket
ya
dense thicket
ez
slow socket
thanks for the help everyone
slow socket
hey guys for my question above, to find the equivalence classes wat i did was i used
m congruent to n(modp) , idk if thats right, then for [1]
m^2 congruent to 3k +1 and i got
[1] = 1, 2, 4, 5, 7
is that right?
wanton summit
So confused. 😭
wooden saddle
Drop out
pearl basin
Can anyone provide a hint on how to reduce (c) to 3SAT? So far everything in class related to 3SAT has been graphs but I don't see how to see this problem as a graph. The formal definition of (6) makes no sense to me.
weary tiger
@wanton summit you should say what did you try to solve the exercise
green panther
oof @pearl basin I'm not sure how to start the reduction to 3SAT but I think the formal definition of 6 can be read roughly as {to get from i to i', along some path j, the reward vector times the cost vector is greater than 0}. So if that graph is acyclic, than that just means there's no way to keep repeating quests and farming resources
wanton summit
@weary tiger I dont really understand the question. Like the notation in the beginning makes no sense to me. The x R\Z. Maybe if I understand that, then I could proceed?
opal crescent
R\Z means the set of real numbers from which you take out the integers
wanton summit
Ah.... Thank you. 😊
pearl basin
But isn’t the reward times the cost vector always positive or zero?
pearl basin
I'm thinking this is more easily reducible to a problem like this: Given a directed acyclic path with weighted edges, what is the largest # of vertices in a path s.t. the total weight of the path does not exceed some value?
Is this similar to some NP-complete problem that I should know? Or am I better off reducing it to 3sat somehow? Because I'm stumped as to how I do that
azure lichen
this looks like knapsack to me
but in more complicated
oh but yea, if you can solve this you can solve knapsack
slow socket
can anyone link me a good place to learn about loop invariants?
sour arrow
@slow socket
"The knot book" pdf is online it's pretty good
slow socket
ty
acoustic valve
party rockers in the hou se tonight
shadow dragon
crystal bough
I subtracted 33 from 100 cuz that's the number of multiple of 3
but there will be multiple of 3 included as well like 99 cuz we already excluded 33(11×3)
So how can I find multiple of 3 which should be included
bitter latch
@crystal bough let's start with 1 to 100, you removed all multiple of 3
but you can include 9 inside it, as there's no 3 in the list
and since there's 9, you can't include 27
and since you don't have 27, you can include 81
it's alternating, so you can work it out
bitter latch
think it in another way
now you have list of multiple of 3
if a multiple of 3, is a multiple of 3 in that list
then it will be ~(~A) = A
and you can put those number back into the list
crystal bough
what do you mean by ~(~A) = A
crystal bough
I see
bitter latch
~A will give you list of multiple 3 in that list
~(~A) will give you list of multiple of 3 in ~A list
you will keep alternate between until you reach list length < 3
crystal bough
hmm
bitter latch
I've checked the actual result, this method works
crystal bough
I don't understand this method
can you show me the solution?
how did you found ~A?
did you subtracted A from total?
bitter latch
~A is just list of multiple of 3
~ will give you list of multiple of 3 in that list
crystal bough
aren't all of them multiples of three though?
crystal bough
right
bitter latch
~ = will gives you (all numbers inside the list) * 3, that is inside in that list too
so ~(~A) = [9, 18, 27, 36, 45, ...]
you can think it's like a frog jumping game (if that's the thing)
circle represents number
bitter latch
yes
bitter latch
3 more
crystal bough
right 3
bitter latch
the total number = floor(n/3)
crystal bough
so how many of them will be added to the list?
bitter latch
the total numbers should be
$\sum_{i=0}^{\lfloor \log_3 n \rfloor} (\lfloor \frac{n}{3^i}\rfloor)(-1)^i $
vital dewBOT
LeFt_HitD:
bitter latch
n = 100 - floor(100/3) + floor(100/3^2) - floor(100/3^3) + floor(100/3^4)
bitter latch
you alternate between plus and minus
crystal bough
yeah thanks!
weary tiger
@heady sedge Given any x in S, you can either:
- put it in A
- put it in B
- put it in C
- not put it anywhere
weary tiger
in other words, no two different sets in the collection have an element in common
in your case, it means that
- A and B have no element in common
- B and C have no element in common
- A and C have no element in common
heady sedge
Ah ok thanks
Also having problems with this
How can i show that 4 of her ftiends will get type C3?
golden cairn
I had a problem on my dicrete midterm today that was: find how many numbers have uniquely 0 1 2 in them between 1000 and 9999. I calculated 126, was that correct?
I assumed that there were 4 options for the 4 positions: (2 2 1 7) (2 2 7 1) (2 7 2 1) (7 3 2 1) and that the first 3 had 28 options and the last one had 42
@heady sedge Maybe (7 4) * 8^3
because 7-4 = 3, and 8 choices for the remaining 3 friends?
analog sonnet
I'm not sure I understand your question. You're looking for the amount of numbers in the set that contains 1000, 1001, 1002, 1010, 1011, 1012, etc?
azure lichen
I think it's "What is the cardinality of the set of all four digit numbers (no leading 0 allowed) in Base 10, such that the digits 0,1 and 2 each appear exactly once"
can't answer it rn though cause in class
slow socket
show that n^2 >= m^3 is a loop invariant in the loop
while 1 <= m do
m := 2m
n :=3n
Can someone explain how they did this. Is confusing me.
golden cairn
@analog sonnet ie: 1025 not: 1102 or 1345
Nvm its 126
I coded a little java program to loop the numbers bc i just wanted to know if i was right
golden cairn
Wat?
proven shard
Nvm
slow socket
@proven shard what?
blissful basalt
Evening All, I was given this in lecture today (sets) as an example and my lecturer said it comes to x = -2 for A that is, I cannot see how it comes to that?
Find simpler descriptions of the following sets: A = {x : x is an integer and x^2 + 2x = 0} B = { x : x is a month not containing the letter r}
craggy gale
To be honest, 0 is an integer and 0²+2×0=0 so 0 is in A too
blissful basalt
We argued that with him, if he said if x was replaced with the integer 0 that it would come out as -2 I fail to see how?
As what you did was logically correct
craggy gale
Not sure what your lecturer had in mind, but for me, clearly A={-2, 0}
blissful basalt
He said that if x=5 that it would return -35 which makes no sense 😅 or is it just me?
craggy gale
There must be a misunderstanding somewhere xd
blissful basalt
Well that's good it wasn't only me 😅 Thanks @craggy gale
ashen magnet
got a question. if i'm supposed to find the elements such that
([0, 1) ∪ (1, 7)) ∩ Z
would i be correct in saying this yields {0,2,3,4,5,6}?
i'm just not sure about the sets in the parentheses. 1,7 can include an infinite combination of numbers.
so in that case would it be
[0,7) ∩ Z = {0,1,2,3,4,5,6}
plush rampart
I'm not sure if this would include 1. While you're taking the union of [0,1) and (1,7), 1 isn't included in either set.
I "guess" the answer should be {0,2,3,4,5,6}
Hope someone corrects me in case I'm wrong!
azure lichen
just because these sets have an infinite number of elements in them does not make them have 1 in them.
The union of [0,1) and (1,7) does not contain 1, as neither of the sets do. Same with 7. Your first answer was correct.
crystal bough
If f(x) is a bijection and g(x) is surjection but not injection then fog(x) might be?
the answer says injection but shouldn't it be surjection?
cuz both functions are surjection
pale epoch
What's the domain and range of both functions?
crystal bough
not given in the question
pale epoch
Then the only thing we can say for sure about fog is that it's injective
fog is only a surjection if the range of g is the domain of f
crystal bough
ah I see that does makes sense but how can we say that it's gonna be injective?
pale epoch
f is injective
hm, wait
You are right
Let g: R -> {0} be constant zero function
Then g is a surjection but not injective
and f(g(x)) is constant, i.e. not injective
So without given domain/range you can say nothing about fog
pale epoch
only if domain/range are the same
if f is the identity function
So, let f: R->R be the identity function
it's bijetive
and let g:R->{0} be the constant zero function
then g is surjective but not injective
and f(g(x)) is constant 0
if f and g have same domain and range
then fog will be surjective, yes
crystal bough
so if range of f is the same as domain of g then fog is gonna be surjective
pale epoch
yeah
crystal bough
thanks!
crystal bough
How can I find number of partial order relations on a set with 3 elements?
I can find number of reflexive and antisymmetric but what about transitive?
stable onyx
how do i derive this function
azure lichen
you do it separately for each interval, and then compute the limits of it at -1 and +1
(which may not exist, in which case it’s not differentiable there)
stray reef
this doesn't belong in this channel
azure lichen
you’re gonna be saying that a lot
stray reef
also hi
azure lichen
I mean, kinda really is, there’s only so many big servers
stray reef
true
stable onyx
oh sorry i don't even know how did i end up on this channel
lofty island
I have a question on #❓how-to-get-help-alpha
lofty island
does anyone know good books for sequent calculus?
tranquil iris
Could someone show an example of the method used here? I know/understand getting the modulus but not proving the divisibility overall
vital dewBOT
savataji:
craggy gale
it's a derivative thing
harsh warren
what do you mean?
craggy gale
$\frac d{dx}(1+x)^n=\frac d{dx}\sum_{k=0}^n{n\choose k} x^k=\sum_{k=0}^n{n\choose k} \frac d{dx}x^k$
vital dewBOT
Tuong:
harsh warren
where did that d / dx come from
i don’t think i’ve seen it before
oh so how do i use it?
craggy gale
maybe you prefer ' for derivatives ?
why talking about series? They are way too complex objects
opal crescent
you could also use the shitty combinatorics formula n * C(n-1,k-1) = k * C(n,k)
but ye derivative is kewl
craggy gale
oh yeah that formula was cool for linear time complexity calculation of binomial coefficients
harsh warren
ok that combinatorics formula thing sounds more familiar
but how do i get the kx to appear and for my summation to start at k=1?
harsh warren
oh i thought you were continuing from where i did till
harsh warren
how come?
opal crescent
$n^{\mathbf{n-1}}(1+x)^{n-1} = (n+nx)^{n-1}$
vital dewBOT
emeric75:
opal crescent
i actually have no idea what's going on in your stuff
harsh warren
oh shit sorry
ok never mind what i did
could you explain how you did yours please
i lost you at “use the beautiful formula”
like where did the n outside the brackets go and why did you suddenly have a kx^k
@weary tiger yeah i didn’t know i couldn’t do that, my bad
opal crescent
$$n(1+x)^{n-1} = \sum_{k=0}^{n-1}n\binom{n-1}{k}x^k$$
vital dewBOT
emeric75:
opal crescent
so yeah it can be shown pretty easily that for any integers $k,n, k<= n,$ you have $$n\binom{n-1}{k-1} = k\binom{n}{k}$$
vital dewBOT
emeric75:
opal crescent
i actually did a small mistake in the middle mb
in particular (in our case for the sum) $$n\binom{n-1}{k} = (k+1)\binom{n}{k+1}$$
vital dewBOT
emeric75:
vital dewBOT
emeric75:
opal crescent
now if you shift the index up by 1, ie k now goes from 1 to n
$$\boxed{n(1+x)^{n-1} = \sum_{k=1}^{n}\binom{n}{k}kx^{k-1}}$$
vital dewBOT
emeric75:
harsh warren
i’m not very sure about this part $k,n, k<= n,$ you have $$n\binom{n-1}{k-1} = k\binom{n}{k}$$
vital dewBOT
ppper:
harsh warren
but i understood the rest of it
opal crescent
that's a thing i don't use very often either tbh
harsh warren
so i just have to try and understand that part and everything will fall into place hopefully
opal crescent
but yeah you can just check using the definition with factorials of the binomial coefficient if you want
harsh warren
but yeah thanks for the help, appreciate it!!
opal crescent
👌
obsidian rampart
stray reef
,rotate -90
vital dewBOT
obsidian rampart
oh sorry bout that.
obsidian rampart
its the same problem
the one that you rotated is just my work on the back of the paper
stray reef
your photo of the exercise sheet contains problems 4, 5 and 6
of those, which ones are you doing
obsidian rampart
#5
vital dewBOT
Ann:
stray reef
this?
obsidian rampart
yes
obsidian rampart
yes
stray reef
ok well
obsidian rampart
that was my work before i had to leave the room.
vital dewBOT
Ann:
vital dewBOT
Ann:
obsidian rampart
correct
vital dewBOT
Ann:
stray reef
split off the very last term from the summation
obsidian rampart
ahh i think thats where i messed up.
stray reef
well
obsidian rampart
i did k+1 = k + k + 1
stray reef
$\left(\sum_{j=0}^k 3 \right) + 3 = 3(k+1) + 3$
vital dewBOT
Ann:
stray reef
and 3(k+1) + 3 is of course equal to 3(k+2)
stray reef
this is the "what we want to show" part
obsidian rampart
ok so how did you know to set them equal to each other?
k+1 = k
because isnt k+1 = k + k+1 ?
stray reef
k+1 is not equal to k + k+1
and i'm not setting k+1 equal to k either
okay so like
let's forget about that problem for a moment
obsidian rampart
👍🏻
stray reef
$\sum_{j=0}^{200} a_j = \left( \sum_{j=0}^{149} a_j \right) + \left( \sum_{j=150}^{200} a_j \right)$
vital dewBOT
Ann:
stray reef
does this manipulation make sense to you?
obsidian rampart
no
stray reef
alright well
ok
so what i did is usually referred to as "summation splitting"
there's no formal name i know of
but anyway
so you know what $\sum_{j=0}^{200} a_j$ means, right?
vital dewBOT
Ann:
obsidian rampart
yes
stray reef
there's 201 terms: a_0, a_1, ..., a_200, all being added together
stray reef
yeah so like
let's say that for some reason i want to consider the sum of the first 150 terms (a_0 through a_149) separately
it doesn't need to be 150 of course
it can be anything
but just for this example
obsidian rampart
ok
stray reef
so what i can do
obsidian rampart
OH ok i see how you got the 149 now.
stray reef
i'm going to write this out using ellipses
obsidian rampart
ok
stray reef
=tex a_0 + a_1 + \cdots + a_{200}
ah fuck sorry wrong command
$a_0 + a_1 + \cdots + a_{200}$
vital dewBOT
Ann:
stray reef
there
obsidian rampart
you're good, thank you for the help.
stray reef
oh, do you not need further explanation on this example? or do you want me to continue
stray reef
alright
so yeah that above is our original sum
now this can also be rewritten as
$a_0 + a_1 + \cdots + a_{149} + a_{150} + \cdots + a_{200}$
vital dewBOT
Ann:
stray reef
right? there's nothing forbidding us from doing that; it's a bit long, but it's still valid
obsidian rampart
ok so let me see if i got this.
so you chose the first 150 out of the 200 then to get to the 200 you added the last part (starting from 150 to 200) in your summation splitting example?
stray reef
yes
i split the sum into two parts: one for the first 150 terms, and one for the rest
obsidian rampart
so you could also split it into 100 then technically?
stray reef
of course
obsidian rampart
instead of 150
stray reef
you can split any way you like
obsidian rampart
ok that makes sense
stray reef
as long as all the terms are accounted for, and you don't accidentally overcount anything
obsidian rampart
yeah
stray reef
the way i chose to split $\sum_{j=0}^{k+1} 3$ is to have just one term in the right part, and the rest in the left
obsidian rampart
and you went to 159 because 0 is your starting point, this makes sense now.
vital dewBOT
Ann:
obsidian rampart
ok im just confused as to how you got that extra +3 part
obsidian rampart
$\sum{j=0}^{k+1} 3 = \left(\sum{j=0}^k 3 \right) + 3$
vital dewBOT
Soraka:
obsidian rampart
here lemme paste it again
stray reef
$\sum_{j=0}^{k+1} 3 = \left(\sum_{j=0}^k 3 \right) + 3$
vital dewBOT
Ann:
obsidian rampart
oh my bad, never used the bot before lol
oh so the +3 would be the base case i did then?