but when i tried to see one at b i got lost
#discrete-math
true hare
sick swallow
the pattern is still very obvious for b
sick swallow
? that is literally how it is defined
true hare
oh im dumb
sick swallow
induction is probably the easiest way
true hare
could you walk me through that, im lost
this is just test review, not a grade, just curious how to even begin to tackle this
sick swallow
it is just fx=1
true hare
how?
sick swallow
i thought u said u tried plugging in values
true hare
i did
sick swallow
maybe try again
sick swallow
wait are u talking about b
true hare
those are for a
true hare
this is my last review question, this is what i have so far
$\varepsilon \in K\land [x\in K \implies axb \in K]$ and $\nexists n\in\bN: w=a^nb^n \implies w\notin K$
vital dewBOT
evnaf:
compact shell
Determine whether the following relation is reflexive, symmetric, antisymmetric, or transitive.
R is a relation on Z where xRy if x+y is odd.
Could someone please explain?
stray reef
what exactly do you need explained @compact shell
are you having trouble applying the definitions of those properties to your relation?
rain stone
@hardy remnant when x < 1, x^2 < x, so the substitution they did wouldn't yield the desired inequality
similarly, when x < 1, x^2 < 1
loud copper
@hardy remnant yo is that grimaldi ?
weary tiger
this sounds a lot like asking for exam help
1-2 hours
specific timeframe
money
only need help for homework assimgent because i have an older professor who cannot explain or email in time
i put in the discription homework help ๐
errant bear
why that specific time zone then
errant bear
why 1pm on a specific date if its just hw
weary tiger
bec I get off work at 1pm est, so if people are availble to help after that time it would be great!
timber garnet
Hello i need some help understanding a proof
The book is discussing the pigeonhole principle
ill just post the proof here i just dont understand the last part. Basically if someone could help with explaining what the "pigeons" and the "holes" are in this solution that'd help. The rest i can do on my own
last flicker
The pigeons are the nodes in your family tree over the last 1000 years and their holes the are the cumulative population of the world over the last 1000 years
Every node must be a member of that population, but there are more nodes than people who could have lived in the past 1000 years, so at least two of the nodes must be the same person
timber garnet
ohhh i see that makes some sense
wintry schooner
hey could anyone help me with this?
"For any integers, a b and c, if a+b is even and b+c is odd, then a+c is odd. Argue why this statement holds.
How do I answer this? im a bit lost haha any help is much appreciated
last flicker
oh
i gave that away
what do you know about the parity of a and b if their sum is even?
wintry schooner
@last timber no i dont know
im quite lost on how to go about this question
how can i explain why this statement holds?
last timber
well look
wintry schooner
so far I have understood that a+b = 2k
last timber
consider for example 1+1 is it even?
last timber
and 2+2 is obviously even
wintry schooner
yea
last timber
but is 1+2 even?
wintry schooner
nope odd
wintry schooner
I think i understand when you put it in that way
last timber
i can extend that by
2+4 even
1+121 even
2+5 odd
3+120 odd
last flicker
generalise that notion
wintry schooner
but im not sure how to explain in terms of a, b and c
wintry schooner
yeah
last flicker
if you add 2 odd numbers
wintry schooner
its even
last flicker
?
wintry schooner
its even
last flicker
and an odd and an even?
wintry schooner
odd
last flicker
so it follows that given a+b is even, a and b must either be both negative or both positive
fyuck
i mean
both even or both odd
last timber
sum even -> both terms of the same parity
sum odd -> terms of different parity
so with that and knowing that
a+b=even
b+c=odd what follows?
wintry schooner
ohhhh
i kinda see now
c in this case would be an odd number
and when a is an even number, a+c = odd
because even + odd is always odd sum
hmmm interesting
wintry schooner
oh yeah
last timber
but since a+b is even a and b are of the same parity
and b+c odd implies that b and c are of different parity
last flicker
consider the case where a and b are both even, and the case where a and b are both odd and see what follows about c and thus about the parity of a+c
i.e. a and b even implies c is odd since b+c is odd, then a+c is even+odd=odd
and the other case
wintry schooner
ahhhh yes okay
@last timber @last flicker thanks guys, your help has cleared it up for me, much appreciated!
last flicker
no worries!
last timber
np
weary tiger
Would relationship R^1 o R would be both symmetric and reflexive
if R (a,b) belongs to A, R^-1 would be (b,a) belong to R. Therefore final mapping would be (a,a)
therefore it would be symmetric, not sure if it is reflexive tho.
lean flume
lean flume
its just a whole in whole weirdly worded question
weary tiger
botn
how you doin'
hey I'm pretty good
are you german btw?
ok, do you know what exhaustion is?
lean flume
how does the method of exhaustion help with the question
weary tiger
it basically means, exhaust each case of n=6, n=7, so on until n=18
botn
are you german
no
why not
have you considered being german
dm me these random things if you need to
ok fine
if you exhibit a sum of 2 primes that equals 6, then you have proven the statement for n=6
lean flume
oh
weary tiger
if you do the same for the rest of the possible n's, then you have proven what is asked
@lean flume what book you using
lean flume
wdym what book idk its an online thing i can show u later
lean flume
yea
weary tiger
nah lol i don't wanna see your homework
lean flume
but it may be a real book too just available online for us
weary tiger
i'm all good
lean flume
kk ๐
weary tiger
nothing
oh
aren't you good at combinatorics tho
not really
oh
disappointed in you
son
lean flume
@weary tiger so what do they mean to write the answer as a sum of two prime numbers
weary tiger
,w prime number
vital dewBOT
Requested by polynomial#4757
lean flume
so list the odd numbers within the range
lean flume
yea my bad lOL
weary tiger
@lean flume
lean flume
all the even numbers in the range
weary tiger
what
lean flume
yes? ploynomicla
weary tiger
lmfao
@weary tiger this guy should be in #prealg-and-algebra
is english your first language
@lean flume
lean flume
no
weary tiger
what is your first language
lean flume
i am just trying to understand the question
weary tiger
lol
ok, then can you do what I suggested earlier?
did you read your book?
@weary tiger this reminds me
list all the prime numbers under 18
lean flume
yes i did
weary tiger
have you learnt about p-adic numbers yet
@lean flume then what did your book say on prime numbers
no
botn
what's your favorite area
of math
lean flume
2,3,5,7...
weary tiger
haven't picked one
i mean
but it will probably be number theory or algebra
intuitively
ohhh
number theory
so you will learn about p-adic numbers
sooner or later?
yes
what's your favorite algebra book?
more nathan, up to 18
I tried to read artin a little earlier this summer but I struggled too much with it
artin is a bit much
i mean
what's your favorite book
lean flume
2,3,5,7,11,13,17
weary tiger
i mean you might not have one just yet
but
any particularly good ones?
that you liked
I was going to say artin is probably the only I have a non-negligible amount of experience with, so that's why I mentioned that
oh
what
so you haven't read an abstract algebra text?
i was going to read one from springer
wanna be study buddies
yea actually, sure
that'd be nice
one sec
and yea nathan, that's right
so
look at it
tell me if you like it
you want to first write 6 as a sum of 2 of the numbers in that list
i had ann looked over it and she said it was good
(they can be the same)
lean flume
so it says the sum of exactly two prime numbers
lean flume
2 and 3?
weary tiger
suppose $n \in \mathbb{N}$ and $n = a_1^{e_1} a_2^{e_2} a_3^{e_3} \cdots a_n^{e_n}$
vital dewBOT
polynomial:
lean flume
okay
weary tiger
does 2+3=6?
lean flume
no but it is less than it
weary tiger
$n$ is prime $\iff a_1^{e_1} a_2^{e_2} a_3^{e_3} \cdots a_n^{e_n}$ = a_1^1$ without loss of generality
ok you like...
might need to get some experience reading simpler mathematical statements
botn
i am just kidding with this guy
but
did you look at the book
I wasn't referencing what you just said
i know
I was talking about how he doesn't understand the original question
i know lol
and yea sure
i was replying to myself
basically
cool
how much of the material do you know there?
i think artin covers a lot more than that
it does not matter that 2+3<6 nathan
but this one is a book we can actually read
lean flume
can u try to simplify the question for me cuz idk if i understand it
weary tiger
nathan
to be honest
you're doing math above your level
I probably know mostly all of the first 2 chapters already and a fair amount of 3 and 4
you need to step back
watch khan academy
i am sure botn will agree
you can't do that problem if you don't know what a prime number is
and you are for sure supposed to know
what a prime number is
lean flume
i real the book but like i have not done much practice because my professor is unabailable online
weary tiger
he might know what a prime number is now since he listed them correctly
i recommend just watching some khan academy
yeah that's fine
but you need more mathematical maturity
have you tried khan academy
lean flume
no
weary tiger
try it
https://media.discordapp.net/attachments/362719706555088896/739201763164553228/unknown.png bumping this since I don't want to have to scroll in case I need it
botn
give me your schedule for the book?
i.e. how often do you want to discuss
hmm
I have nothing I need to do today so I could start reading it right now
and talk about later today to start
tepid lantern
How far away are to solving the Goldbach's conjecture?
weary tiger
anyone who answers that will be guessing
@weary tiger no botn i have a time machine
1 me
0 you
tepid lantern
Isn't the Goldbach's conjecture easy?
Take two arithmetic progressions
6n+1=1,7,13,19,25,31,....
6n+5=5,11,17,23,29,35,....
note that if 6n_1+1 is divisible by f then 6(n_1+xf)+1 are all terms in 6n+1 divisible by f
note that if 6n_1+5 is divisible by f then
6(n_1+xf)+5 are all terms in 6n+5 divisible by f
6n+1 is only divisible by odd number and not divisible by 3
6n+5 is divisible by odd number and not divisible by 3
able to recreate all even numbers
6n+5= 5,11,17,23,29
6n+1=25,19,13,7,1
25+5=30,
11+19=30,
17+13=30,
23+7=30,
29+1=30
6n+1=1,7,13,19,25,31
6n+1=31,25,19,13,7,1
31+1=32
25+7=32
19+13=32
13+19=32
7+25=32
1+31=32
6n+5=5,11,17,23,29
6n+5=29,23,17,11,5
29+5=34
23+11=34
17+17=34
11+23=34
5+29=34
using pigeon hole to fill terms with possible composites.
in n terms where n is odd there is at most 1 term in arithmetic progression divisible by n
In two arithmetic progressions there are at most 2 terms divisible by n
repeat for n,n-2,n-2-2,n-2-2-2,....5
stop at 5 because arithmetic progression does not generate numbers divisible by 3.
There are at least 3 pairs of numbers where each number in the pair are not composites.
In 6n+1, 6n+1, 2 of these pairs will have unit 1 leaving 1 pair to have two numbers to be prime.
In 6n+1, 6n+5, 1 of these pairs will have unit 1 leaving at least 1 pair to have two numbers to be prime. If n is even then assume the last term contains non-prime numbers and pigeon hole away the last term into another term which is not the first term.
quaint star
I haven't read this yet, but are you asking if this is a proof of the Goldbach conjecture?
tepid lantern
Yes this should be the proof to the Goldberg conjecture
weary tiger
Damn
quaint star
Fuck. I was going to sleep now, but now I want to be enlightened
This is very unreadable to me, so I will go through it bit by bit and ask you questions if you care to answer them
Let (xn) = (6n+1) and (yn) = (6n+5) be arithmetic sequences. If 6n+1 is divisble by f, then (6n + xf) + 1 is divisble by f (x and f are integers here, I hope, or what ?). I agree. Why is this (6n + xf) + 1 in the sequence (xn) though? This is only true if xf is divisible by 6.
If 6n+5 is divisible by f then (6n + xf) + 5 is also divisible by f. Again, I agree, but why is it in the sequence (yn)? Only true if xf is divisible by 6.
honest barn
Wait is this guy saying goldbach is easy omegalol
quaint star
6n+1 and 6n+5 are both divisible only by odd numbers and is not divisible by 3. I agree
tepid lantern
opps put th3 brackets in the wrong place 6(n+xf)+1 and 6(n+xf)+5
quaint star
Okay, then I agree
up to here
Now you say able to recreate all even numbers
What do you mean? Are you saying every even number can be written as a sum of a term in (xn) and a term in (yn)?
Oh, sorry, I think I misunderstood
You are saying any even number is either the sum of two terms in (xn) or the sum of two terms in (yn) or the sum of a term in (xn) and a term in (yn)? I that right?
Is*
tepid lantern
yes
quaint star
I think I agree. Let me just convince myself
Yes, I do
"Using pigeon hole to fill terms with possible composites"... I don't understand. Explain ?
tepid lantern
okay the first composite in 6n+1= 1,7,13,19,25 is 25. want to count composites by counting numbers which are multiples of odd numbers 5,7,9,...
therefore in 6n+5=5,11,17,23,29 we would count 5 as a possible composite
quaint star
I do not understand what you mean by counting 5 as a possible composite?
tepid lantern
well all the numbers in 6n+1 where 0<=n<m if 6n+1 is a composite then 6n+1=a*b where 1<b<=m
quaint star
Yes, that's true of any composite number
But I don't understand why you count 5 as a composite when it is prime? What does that mean?
tepid lantern
I can not directly count primes but I can count numbers which are multiplies of an odd number 5 or greater
And after removing all numbers divisible by 5 from 6n+1 where 0<=n<5 either left with prime numbers or the unit number 1
quaint star
Okay, I still don't exactly understand, but let's move on to your other claims. Once I agree to all your claims, then we can look at the general argument.
In n terms where n is odd there is at most 1 term in arithmetic progression divisible by n. Are you saying that in (xn) or (yn), for any n consecutive terms, at most one of terms can be divisible by n?
tepid lantern
Going one step up there only exist one term divisible by 7 in 7 terms of 6n+1 where 0<=n<7 . So in 6n+1 where 0<=n<5 all terms are not divisible by 7 and check for terms divisible by 5. If all composites are divisible by 5 and 7 in 6n+1 where 0<=n<7 have succeed
quaint star
I think I agree with this
In two arithmetic progressions there are at most 2 terms divisible by n. So you are saying at most 1 term in (xn) and at most 1 term in (yn)?
quaint star
There are at least 3 pairs of numbers where each number in the pair are not composites. I don't understand. What are the pairs?
tepid lantern
ok
the pairs for 6n+1,6n+1 are
31+1=32 (31,1)
25+7=32 (25,7)
19+13=32 (19,13)
13+19=32 (13,19)
7+25=32 (7,25)
1+31=32 (1,32)
quaint star
Okay, but why do you say there are three pairs where both numbers are not composite? What's the proof?
tepid lantern
1,7,13,19,25 one number divisible by 5
32,25,19,13,7 one number divisible by 5
All composites must be divisible by 5
therefore 3 pairs of numbers add up to 32 where all numbers in each pair are not composites
quaint star
This is an example
Where is your proof that it's always true?
All composites must be divisible by 5 is also not true
errant bear
5 clearly divides 6 though
quaint star
It's nearly midnight here, so do you think you can come up with a proof quickly or will you think about it and ping me so I can look at it when I wake up?
tepid lantern
no I can not come up with a proof quickly
quaint star
Okay, if you have an idea of why it's true, try to write a proof and @ me so I can read it. If you realize you made a mistake, let me know too. Sorry I can't stay awake longer.
obtuse lance
Yes this should be the proof to the Goldberg conjecture
@tepid lantern I hope this is a trolling attempt to sneak your way out of saying you never claimed to prove Goldbach lol
weary tiger
@obtuse lance thanks
edgy glen
So I'm just curious to learn a bit about combinatorial structures, and looking up some basic stuff on generating functions, I feel like I'm misunderstanding something about notation. For example, a video I'm watching makes this assertion, which is clearly visually false in the way that I would normally think about such notation:
I mean, pick any X and this is not true. It's even nonsensical for x=1
weary tiger
x cannot be 1 for that example
edgy glen
Right, that's what I'm saying
edgy glen
Ohh, it's talking about a restricted domain
naive saffron
These things are called power series, and the infinite sum only make sense (converges) within some interval (a single point, a bounded interval, or the whole real number line). But for generating functions you usually don't worry where the function converge, you only need to know that the power series product of the function is the product of the power series
weary tiger
๐
royal dirge
Is there a rule that I'm forgetting
or do I have to manually solve for the cardinality ?
stray reef
if you know |S| then it's not that hard to find |P(S)|
edgy glen
Is there a simple formula for ${n \choose 1} {n \choose 2} ... {n \choose n}$
vital dewBOT
andrew_rpg:
edgy glen
Sorry that should be ${n \choose 1} + {n \choose 2} + ... {n \choose n}$
vital dewBOT
andrew_rpg:
stray reef
the latter is much easier to simplify than the former
obtuse lance
hint: binomial expansion
edgy glen
I had a feeling it was something related to that. But it's been 15 years since I looked at Pascal's triangle, and the details are fuzzy
obtuse lance
well now you know what to do
stray reef
$\sum_{k=0}^n \binom{n}{k} 1^{n-k} 1^k$
vital dewBOT
Ann:
stray reef
this is almost your sum
edgy glen
Not sure why ya'all are dancing around it...
obtuse lance
we're here to help you not give you answers
if it's been 15 years since you looked at pascal's triangle and you're trying to solve this problem, then you should learn the binomial theorem and make it 0 years
edgy glen
So it just simplifies to ${2^n}-1$
vital dewBOT
andrew_rpg:
naive saffron
That's the right answer
stray reef
stray reef
desmos is your friend
it'll look similar to the staircase-like graph of the floor function, just compressed and shifted
edgy glen
So if I have n distinct objects, and I want to refer to all ${2^n}-1$ ways to group them (e.g., for A, B, and C, I would be referring to the list A, B, C, AB, AC, BC, ABC), is 'combinations' the right term? In set theory, the term would be 'power set', I believe, but I'm not sure the corresponding term in combinatorics.
vital dewBOT
andrew_rpg:
edgy glen
Ah right
edgy glen
I guess it would be "combinations of any size"?
weary tiger
how can i help
edgy glen
Well, I'm not interested in the empty set, which, as you point out, the powerset would include
stray reef
stray reef
reasonably good i guess but you're risking getting wrong-channeled
stray reef
can you please stop sending a message containing just my name and that fucking smile emoji
it gets old after seeing it for the (n+1)th time
anyway ok what is it
is it another linalg problem
if so then please post it in the right channel
weary tiger
?
edgy glen
So if I have n positive numbers: $a_0, a_1, ..., a_{n-1}$, and they are in ascending order, but not necessarily distinct, I'm trying to figure out how many possible ways there are to arrange the sums of all $2^{n-1}$ groupings of them in ascending order.
vital dewBOT
andrew_rpg:
stray reef
2^n - 1, not 2^(n-1).
edgy glen
Yes, thank you.
edgy glen
Yeah, I've been trying to figure out how to word it correctly
stray reef
did this come from a problem you were doing
edgy glen
No
stray reef
unfortunate
edgy glen
I mean, it's one part of a problem that I remember discussing back in college that I'm ruminating on again, related to the Shapley-Shubik power index.
But this specific question is one that I'm asking myself
stray reef
are you trying to count the ways to arrange the nonempty subsets of {0, 1, ..., n-1} in ascending order by the sum of the corresponding a_i?
or do you not distinguish between two subsets that have the same sum
edgy glen
I think, to start with, it makes the most sense to distinguish between subsets with the same sum. Otherwise, I suspect it gets muddled really fast
weary tiger
andrew
since you weren't familiar with the infinite series you posted earlier
i feel like you aren't familiar with mathematics in general
so it may be wise to stop trying to abstract things before you understand them intuitively
edgy glen
Um, ok
edgy glen
That's a really vague question...
weary tiger
ok, what's the derivative of -cos x
edgy glen
Maybe we stick to the topic at hand...
weary tiger
i mean if you can't answer that, then you are not familiar with mathematics
hence, you should not try to abstract not so trivial concepts
prior to understanding them intuitively
weary tiger
lol
gatekeeping
are you serious
it's literally the first kind of heuristic advice you would get in any book
in fact
i hesitate to call it heuristic advice
it's just common sense to take a simple example prior to trying to generalize
errant bear
stray reef
@worthy palm nothing, poly just felt the need to be rude
mint shore
yo, generating function question:
i kinda get that a generating function is a fancy way to portray a power series, but i don't get something
what do you plug in x? or is it not that kind of function
this for example
(text says: Generating function of 1, 1, 1..)
what role does x play here, if any
or this for example
there's a sequence
a(n) = 3
then that's the generating function?
how does that like, make sense
pale epoch
you plug nothing into x
mint shore
then why does x exist
pale epoch
its a formal power series
you can manipulate it to solve recurrence relations
i guess you will see later, why it is done
the x always just remains an indeterminate
last timber
if u want u can plug x which is in radius of convegence and get value of function for that series but for discrete math you can treat x^n as roughly carrier of nth term
pale epoch
what
convergence for generating functions are disregarded
in fact, it doesn't have to converge at all
and we don't consider it a function in the normal sense
it is just a convenient way of encoding an infinite series
mint shore
so basically it's a sum from the 0th term to the inf term, loosely speaking
much like a formal power series would be i guess
last timber
wel yes, that is what second part of my statement says
for discrete math you can treat x^n as roughly carrier of nth term
pale epoch
why would you plug in anything ever
mint shore
dunno, generating functions always have been the toughest part for me
pale epoch
the fact that is a sum is also unimportant
the nice thing is that the coefficient of x^n is the nth term of an infinite sequence
this is just convenient for writing it down
and you can manipulate it more easily
mint shore
so the gist of it is that a generating function is just a convenient way to write a formal power series, and from the generating function i can get a sequence formula
pale epoch
a generating function is a formal power series
its a convenient way of encoding the information of an infinite sequence
you will probably use them as the main tool to solve recurrence relations
mint shore
pretty much
we have 2 ways to solve a recurrence relation (this sem at least): characteristic equation and generating functions
i already have char eq down
but like
that's all there is to a generating function?
just a power series?
*formal
pale epoch
ye
like, the sum part is really unimportant
its just that you can get the nth part of the sequence by looking at the coefficient of x^n
mint shore
...that's it? i feel so bad for not being able to grasp that concept during the sem
mint shore
my professor has such a hard on for generating functions so i always treated it as a behemoth of work
but like, this is really idk
simple?
i'll solve some exercs to get it down but man that really clears things up for me
thanks tons
pale epoch
its really formulaic
you can solve a general recurrence relation with it
at least a linear one
there are a lot of opportunities to do arithmetic mistakes tho, as it usually involves a partial fraction decomposition
mint shore
yes, but as of now i'm only using them for recurrence relations
mint shore
is it normal to use convergence to get the generating function of a sequence?
pale epoch
convergence of what
mint shore
this is from my powerpoints, one sec for me to translate
says:
find the generating function A(x) of the sequence a(n) = n + 1
a(n) is the convergence of b(n) = 1 with itself, since then proves
the powerpoints are a literal mess i cannot make much of them
mint shore
just asked my brother, i'll clean write what is apparently a full solution and check with you if it's actually the
fucking correct way to solve a recurrence w gf
uploading now, sec
@pale epoch hope my handwriting is legible
but yea
this is it
i still don't get why the fuck convergence is being used
pale epoch
@mint shore ok, let me comment on what you did in the first thing
you are not multiplying a sequence by x^n to get the generating function
its simply that $A(x)= \sum_{n=0}^\infty a_nx^n$ is the generating function
vital dewBOT
Lochverstรคrker:
pale epoch
then what you are doing on first page seems correct
you plug in the recurrence relation, manipulate the series
2nd page also seems ok, i cba to verify it
but it is normal to use convergence of the series
and treat it as a geometric series
the series actually does converge for small x, so that's fine
even though it is not really important
the 2nd thing you posted, first page seems fine
2nd page as well, you need to break down the sum further, then you can write down A(x) = some fraction
and treat it as you did before
(or do partial fraction decomposition)
cerulean ore
Is it possible to solve this recurrence using master's theorem? T(n) = 8T(n/3) + 2^n
I am thinking about to put m = 2^n, which gives log2(m) = n.
Which makes T(n) = T(log2(m)) = 8T(log2(m)/3) + m
comparing with :
junior mantle
and you have f(n)=2^n, which is not a polynomial right? So I think you can't solve it with Master's Theorem?
cerulean ore
Got it! Our teacher said that it is polynomial.
And it can be solved using master's theorem
Thanks a lot wilston!
cerulean ore
My teacher is a very egoistic person, according to him he is always right.
quaint star
Is your teacher me? I am also always right.
cerulean ore
@quaint star Will you say 2^n can be solved by Master's theorem?
~~btw I agree, Kaori is meant to be with Arima Kousei ๐ญ ~~
@junior mantle ๐ญ
quaint star
I don't know what Master's theorem is, lol
Btw, not knowing is not the same as being wrong. So i am still always right.
cerulean ore
Then you are not my teacher. He will say anything just to showoff.
ablahabalahablah, see? I am right.
quaint star
Oh, in that case: Yes it can be used! You just have to know how to do it. I of course know how to do it, but you still need to learn. So go figure it out!
mint shore
i'm having a bit of trouble understanding these 2 transitions
this is generating functions btw
this was the leadup up to that part
leads to A(x) having this form
then somehow in the example convolution is being used?
it's 2 sums
but then in the 2nd transition how does the 1^(n-k) just up and dissapear?
junior mantle
1^(n-k) will always equal to 1
for whatever values n and k be
which is why we can just ignore that
mint shore
fair enough ig
but what about the first transition?
i get why it's broken down to 1/(1-x) and 1/(1-3x)
but i don't get how we get to the double sum
let me scribble something down
sec
yea no i don't get it
junior mantle
Hang on
Personally I would multiply like this #discrete-math message and apply decomposition fraction to divide it into several power series..
I'm not quite sure why they just make it into a double sum tho ._.
mint shore
me neither
so whether i use fraction decomposition or double sum it's the same thing?
because i don't feel like struggling with double sums anytime soon
junior mantle
Personally I think it would be safer to go with the fraction decomposition route, since I don't really understand the double sum one lol
Hang on, I want to check something first
$$\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n$$
$$\frac{1}{1-3x}=\sum_{k=0}^{\infty}3^k x^k$$
vital dewBOT
Wilston Lynx:
junior mantle
By multiplying them, we'll get.. $$\frac{1}{1-x}\frac{1}{1-3x}=\left(\sum_{n=0}^{\infty}x^n\right)\left(\sum_{k=0}^{\infty}3^k x^k\right)$$
vital dewBOT
Wilston Lynx:
mint shore
oh yea
just solved it with fraction decomposition
it's literally
1000000000000x easier
junior mantle
I found this but it's for finite series tho :/
From random Googling lol
Yeah I honestly know what happened to the first line, sorry man
junior mantle
Yeah I mean, idk how did they got into double sum like that--
when i can just do the simplest thing ever
agree lol
mint shore
thanks tons dude
past spire
You can work out the double sum with the cauchy product since both series converge absolutely for $\abs{x}<\frac{1}{3}$
vital dewBOT
Ceana:
junior mantle
Well not to mention that Partial Fraction Decomposition is a simple thing to do, but I think it's easier to apply here than the double sum method
mint shore
i don't remember if i've done cauchy product, i remember cauchy being mentioned in 1st sem but not any specifics
junior mantle
Ah, Ceana is right, the double sum is from the Cauchy Product
past spire
https://en.wikipedia.org/wiki/Cauchy_product, doesnt make it easier than fraction decomposition tho
mint shore
classic uni: hey here's the most roundabout way to do this and not use this simple thing
not to say that double sums and cauchy aren't useful but like
if i can do some simple algebra and not
that
hollow bloom
I just started with Graph Theory, and I have some question regarding to matching. If we are only talking about matching for question 9b, is it necessary to mention all of the vertices for matching?
Or just in general do we have to use all the vertices for a normal matching
wispy vortex
Hi everyone! can someone direct me to some resources on bounded functions and their applications?
Thanks in advance ๐
shell jewel
Or just in general do we have to use all the vertices for a normal matching
@hollow bloom no. It suffices to show a subgraph having non-adjacent edges
hollow bloom
So just showing one pair of edges that are matching is good enough to call that sub graph matching?
shell jewel
Yes
hollow bloom
Gotcha
shell jewel
But they have to be non adjacent, in other words not share a node
Now a maximal partition is one that has the maximum amount of edges satisfying this property
hollow bloom
I see
Then Iโm not sure for this question
Because I think this is referring to perfect matching
I have to show all the vertices are matching
And have an edge
Right?
I canโt just show one pair of perfect vertices
And call that perfect matching
hollow bloom
Lemme find the definition gimme a second
A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching.
A matching (M) of graph (G) is said to be a perfect match, if every vertex of graph g (G) is incident to exactly one edge of the matching (M), i.e.,
Itโs like it fit the matching conditions
But also every vertex have only one edge
Iโm not too clear about this either since I just started learning this
shell jewel
Yeah thats about it
I quickly skimmed wikipedia haha
But why are you assuming the question is asking about perfect matching
hollow bloom
Xd
Because like in the question it referred to pairing of adjacent vertex
So I believe it is talking about perfect matching
If not then like both questions it would be a matching
If it is not referring to perfect matching
shell jewel
Okay gotcha
So it is a pairing of adjacent vertices but still is a matching by the normal definition of matching
So i dont think this is possible im b
hollow bloom
Mhmmm
Wait for perfect matching it is impossible right?
And normal matching is possible
hollow bloom
Understood
shell jewel
Normal matching is possible since you dont have to get all vertices
hollow bloom
Yea
If you donโt use that vertex
The degree is 0 right? So it fits the definition of normal matching?
shell jewel
I am actually not sure if the definition in this question is basically perfect matching. I mean in this question they both fail. But I need to think about it
shell jewel
Srry i am a bit sleepy
hollow bloom
All good
I can email the professor
To clear this up
๐
Thank you so much for the help regardless โค๏ธ
shell jewel
No problem, good luck with you course ๐
errant bear
weebs
cerulean ore
How to solve this?
Firstly we calculte n^logb(a) which is n^log2(5).
Now comparing it with f(n) = n^2 logn
This is not case 2, looks like case 1.
since we can do n^(log2(5)-.23) is n^2.
How do I compare this with n^2 logn?
cerulean ore
So much confused by polynomially larger and smaller ;_;
leaden pebble
isnt those the shigatsu character names?
cerulean ore
Yes, Your Lie In April.
isnt those the shigatsu character names?
@leaden pebble
leaden pebble
@cerulean ore wat you trying to solve exactly
mystic breach
Hey, how can I find the number of 1s in the binary representation of n?
I actually need to sum those values up so I was looking for an explicit expression for it
quaint star
I do not believe there is an expression for it purely in terms of n.
But I'm open to being corrected
cerulean ore
@leaden pebble Trying to learn the Master Theorem.
leaden pebble
ah
weary tiger
livid shadow
pallid lintel
im trying to do all my computerbility assignments in latex (to learn latex) this semestor but i came to a stumbling block, how do i do something like this in latex
couldn't find anything on the internet..i think i'll just draw it
weary tiger
look tikz-able
pallid lintel
sorry if wrong forum, it is discrete math tho
weary tiger
yo im also doing those
state diagrams
oh we learned about those in a CS class, not math
chrome gull
@pallid lintel don't make it in latex, make it in inkscape ๐ you can include latex code in inkscape and then export it as a pdf that can be imported into a latex document
sharp iris
Inkscape is great, agreed
pallid lintel
i made a pretty good picture with it, thanks friends
dusky drift
can u guys help me in discrete?
stray reef
๐
last timber
quaint star
Did you figure it out? Lol
Everyone is waiting for the chance to show off their big brains
eternal plover
We're all raring
last timber
Everyone is waiting for the chance to show off their big brains
@quaint star especially poly
quaint star
Yeah, they are definitely lurking waiting for a question directed at someone else
umbral summit
If I have a set A={1,2,3,4,5,6,7,8,9} and will the pigeonhole principle apply if I select 5 integers from A, and at least one pair must have a sum of 9
what about 4 integers
I said 4 no it does not apply, 5 yes it does apply
not sure if that is right
last timber
well
this is true that 4 is not enoug
because {1, 2, 3, 4}
or {1, 2, 3, 5}
{9, 8, 7, 6, 5) btw
@umbral summit
umbral summit
but would 5 be enough for it to apply
last timber
{9, 8, 7, 6, 5) btw
@last timber no pair gives 9 as a sum
last timber
but existence of selection such that pair giving 9 as sum is enough
to disprove your statement
6 looks to be minimal satisfying set
umbral summit
but I thought it was like if (1,8) (7,2) (3,6) (5,4) are the total pairs summing up to 9 and since there are 4 then pigeonhole applies because 5 > 4
I checked in the textbook and it says it applies
@last timber
this is the explanation it gives
took me a while to find this
oh wait sorry
I mistyped the question
its only {1,2,3,4,5,6,7,8}
my mistake
last timber
ah ok
pale valve
sour arrow
Ye
flat wedge
hello
can anyone help me with predicate calculus ?
im trying to conclude something but i cant seem to do it.....
sour arrow
Ye
flat wedge
How can i conclude this?
From a and b
The (X) is supposed to be for all X,
The Ex kinda things is for some X,
And the upside down L is not(~)
hardy remnant
how the heck am i suppose to find the formula
isnt the formula already 1/2^n
this is for induction
weary tiger
Have you done the โhintโ yet?
hardy remnant
are you saying if P(1) is true?
weary tiger
No, list out some sums for small n
There will be a clear pattern
You canโt see if P(1) is true if you donโt have a โPโ lol
quaint star
The edge set?
copper ore
yeah
quaint star
If is saying there is an edge between every pair of people Pi and Pj. What do you not understand?
The edge set is the set of all the edges, and an edge between Pi and Pj is indicated by PiPj
quaint star
Oh, PiPj and PjPi are the same edge, so it doesn't matter
So without the restriction, the set is the same. I think they just want you to write edges with the lower subscript first
And it shows that $i \neq j$
vital dewBOT
Lunasong:
quaint star
Np
static maple
conceptually why is (13 pick 1) times (12 pick 1 )way bigger than (13 pick 2)
weary tiger
It's part of the hypothesis
copper ore
discrete math class but not really a discrete math question
what does the a' mean?
static maple
i think of 13 pick 2 as picking 2 distinct elements from 13 set, so 13x for the first and 12x for the second, but its half of that and Im not sure whats wrong with how im thinking of it
oh okay i understand now
yep
feel a little dumb, thanks for the help ๐
copper ore
how do you write for every unique A in math notation?
i know the upside down A would be used for for every
but what about unique
gleaming zephyr
!
sour arrow
What would that represent? Haha
It's either "for all" or it isn't. I don't see room for the "unique" bit
We do have a sensible "there exists a unique"
hardy remnant
are you talking about "there exists a"
stray reef
what do you even mean by "for all unique a โ A"
shell jewel
@copper ore can you tell us your entire statement. Although i dont think the 'unique' word would be necessary.
eternal plover
Yeah it's not unique if there's more than one
stray reef
R is a dummy variable in the specification of Z, and even then it denotes a relation on A and not a function from A to A
so no, your approach is nowhere near correct
stray reef
try writing out Z for small values of n and see if you notice a pattern
weary tiger
ok
stray reef
2^(n(n+1)/2), and yes this is correct
weary tiger
cheers
copper ore
also why does V have the n - 1
wouldn't that make the number of vertices an odd number
copper ore
oh right
pale epoch
E is basically
you number your vertices
then you connect each to the one before and next
to create a "circle"
and then connect each one to the one exactly opposite
hollow bloom
A consequence of this relationship is that if I is an independent set of largest possible size in a graph, then V โ I will be an edge cover of smallest possible size. So finding a maximal independent set is equivalent to finding a minimal edge cover
If V is the set of vertices, does this statement apply to any graph?
naive saffron
The degree of a vertex can only be 1,2,...,n-1
I assume n is the total number of vertices
copper ore
yeah true
but i guess if they specify it's not then it's not lol?
like in this case i guess
cerulean ore
isn't log(n) the answer?
After submitting the homework it says ln(n) is the wrong answer
stray reef
that's cause it is
stray reef
also it depends on the value of T(1) i think
it might be either Theta(1) or Theta(1/n)
cerulean ore
How do I find the summation of 1/(n*(n-1)) + 1/((n-1)*(n-2))+...?
vital dewBOT
Commander Vimes:
last timber
then magic will happen
cerulean ore
@last timber It gives
An + B(n-1) = 1
(A+B)n - B = 1
If n = 1
A + B - B = 1
=> A = 1
If n = 0
B = -1```Sorry for the late response, I did partial fraction last time in 2016.
last timber
i mean what have you got when expanded to T(1)?
cerulean ore
There is nothing given for T(1) in the question.
cerulean ore
T(n-1) = T(n-2) + 1/((n-1)*(n-2))
T(n-2) = T(n-3) + 1/((n-2)*(n-3))
.
.
T(2) = T(1) + 1/(2*1)
=>
T(n) = 1/(n*(n-1)) + 1/((n-1)*(n-2)) + 1/((n-2)*(n-3)) + .. + 1/(3*2) + 1/(2*1) + T(1)```ok
vital dewBOT
Commander Vimes:
last timber
now notice something in decomposition you've done
cerulean ore
Oh!
So, basically if an expression is 1/(i*(i-1)) so, it can be represented as (1/i)-1/(i-1)
sum(i=2 to n) : (1/i) - sum(i = 2 to n): (1/(i-1))
Summing two different sequences.
Beautiful!
honest barn
I think your signs are backwards. It should be 1/(i -1) - 1/i I think
cerulean ore
Agreed, thank you for correcting!
@honest barn So, T(n) = T(1) + (1 + 1/2 + 1/3 + ... + 1/(n-1)) - (1/2 + 1/3 + 1/4 + .. + 1/n)
=> T(n) = T(1) + 1 - 1/n
=> T(n) = T(1) + (n-1)/n
honest barn
Idk I just saw that one thing and thought it looked off
stray reef
not enough info to make that conclusion
if T(1) = 100 then T(n) will not be ฮ(1/n)
the exact solution to the recurrence is $$T(n) = (T(1)-1) + \frac{1}{n}$$
vital dewBOT
Ann:
stray reef
if you want this to be ฮ(1/n) then T(1) will have to be 1, otherwise the constant term is nonzero and outgrows 1/n
cerulean ore
Thank you very much! I will have to tell this to my instructor now.
(Although he doesn't care. He teaches algorithms without proving the correctness.)
pale epoch
understandable, that's the hardest part
last timber
it you were required big-Oh you could safely choose O(1) but bruh
loud dagger
so i came to the conclusion that 3^(131) is congruent to 3 mod 5, but now im being asked what the rest is congruent with
i mean my conclusion lead me to the rest being = 3
so what is the rest congruent to?
i dont get it ๐ฆ
loud dagger
So i showed my teacher that 3^141 is congruent with 3 mod 5, which means the rest = 3, now as a followup question im asked only this:"What is the rest congruent with, which alows your solution to work"
so i tried to say that there is an integer n so that 3^131 = 5n+3
stray reef
"the rest"?
loud dagger
sorry rest = remainder in swedish
last timber
still quite unclear
last timber
well if 3^131 is congruent to 3 mod 5 it means that 3 is remainder of 3^131 divided by 5
loud dagger
exactly
last timber
and to what is congruent 3 then lol
are u sure that you are not required to justify why it is so?
loud dagger
i sent a message asking for explaination
or rather a clarification of wtf im supposed to do
weary tiger
isn't 3^131 congruent to 2 mod 5?
3^2 = 9 and 9 mod 5 = 4
((3^2)^65) * 3 = (4^65) * 3
4 mod 5 congruent to -1 mod 5
-1^65 * 3 = -3
-3 mod 5 congruent to 2 mod 5
weary tiger
ye then it's congruent to 3 mod 5 using the same procedure
loud dagger
ye
magic flax
hi i have no idea how to approach this problem :(
like i dont even see why they mentioned that the job list is truncated, how does that affect the question?
brittle sorrel
Can someone help with this?
obtuse lance
I'd try to cook up something where there are k * n choose k of some objects
once I find that, then try to see if I can count it an alternative way with the other thing
brittle sorrel
hmm, I dont understand, what do you mean
honest barn
You can show combinatorial identities by counting the same thing two different ways
Like, I want to count the number of ways I can choose x things out of y things or something
and you count the number of ways in one way where the answer is k * (n choose k)
and a different way where it's n * ((n - 1) choose (k - 1))
reef pawn
Hi can I ask my question or is this room taken?
stray reef
seems free for the time being, given that it's been silent for like 2 hours
reef pawn
alright awesome
this question asks for a contradiction proof
I don't understand how the initial statement is true though
because for some values of a the p is false
even numbers that is
stray reef
ok so you're asked to prove that for all a โ Z, if a^2 - 2a + 7 is even, then a itself is odd
reef pawn
ahhh
stray reef
assume a โ Z such that a and a^2-2a+7 are both even
use this to arrive at a contradiction
stray reef
no
reef pawn
divisible by 2 inside the equation that is
stray reef
the question is properly phrased as $$(\forall a \in \bZ)(2|a^2 -2a+7 \implies 2 \not| a)$$
vital dewBOT
Ann:
reef pawn
yeah that makes sense thanks
so the first part implies the 2nd part is true
and one more question can I take the opposite (the not) of any of the two sides
does it matter?
for contradiction proof
stray reef
to prove $P \implies Q$ by contradiction you assume $P \land \neg Q$ and arrive at a contradiction
reef pawn
ahh okay so leave p as it is and take the NOT of q
stray reef
if you want to phrase it like that...
vital dewBOT
Ann:
compact shell
Let (A, R) be a total order where |A| = 6 How many edges (including loops) are there in the associated directed graph?
It should be 6 * (6 - 1) right?
honest barn
I donโt think it is either
Pretty sure itโs supposed to be 15
Err...
I guess 21
If you count self edge
copper ore
yeah
honest barn
Youโre multiplying by 1
sick swallow
he is multiplying by 1 bruh
copper ore
what
honest barn
Thatโs the same thing