discrete-math

[remote island]

In graph theory, is saying that two vertices v_i and v_j are k-edge connected equivalent to saying that there are k paths between v_i and v_j? Or does that not necessarily always hold?

[stray reef]

one would think that k-edge-connectedness is a property of a GRAPH, and not of an individual vertex or a pair of vertices.

[remote island]

The textbook I'm using has defined k-edge connectedness for graphs in terms of k-edge connectedness of vertices

[stray reef]

ah.

right. that seems to make sense

we say two vertices are k-edge-connected if you can find a path between them in the graph even if some k-1 of its edges are cut

[remote island]

But that does not necessarily translate into the existence of k paths between the aforementioned two vertices, right?

[little prism]

I think it does

[stray reef]

i also think it does

[little prism]

iirc mengers theorem says something like that

[stray reef]

and there might even be an elementary proof

sort of algorithmic

let our vertices be u and v

find a path, any path, from u to v. call this P_1.
forbid an edge in P_1. there will still exist a different path from u to v. call that P_2.
forbid an edge each in P_1 and P_2, and find a third path P_3 and so on...

[little prism]

just looked up mengers theorem. it says that there are k edge-disjoint paths iff it is k edge connecteds. so even stronger

[remote island]

Right

Then why not just define it as the existence of k paths? Seems like a more straightforward definition to me 😄

[remote island]

Theorem: In every simple graph, there are an even number of
vertices of odd degree.

Proof: The proof is by induction.
Inductive Hypothesis: The inductive hypothesis, P(n), states that in every simple graph with n vertices, there are an even number of vertices of odd degree.
Base Case: The base case, P(1), is trivially true. Since a graph with one vertex has no edges, therefore, it has an even number of (zero) vertices of odd degree.
Inductive Step: Assume that P(n) is true. Now consider a simple graph G = (V, E) with n + 1 vertices and eliminate an arbitrary vertex v (along with the edges incident to v) to obtain G' = (V', E'). Since G' has n vertices, then by P(n), it has an even number of vertices of odd degree. The rest of the argument is by cases:

Case 1: v had zero neighbors.
Then, the addition of v to V' in order to obtain the original graph G, does not affect the degree of any vertices in G', and v has an even degree (zero), so the number of vertices of odd degree in G is still an even number. Therefore, P(n + 1) follows in this case.
Case 2: v had s > 0 neighbors, where s is an odd number.
Then, the addition of v to V', and the addition to E' of the edges incident to v in G, affects the degree of an odd number of vertices. There are now two subcases:
Case 2.1: v had an odd number (2k + 1) of neighbors of odd degree, and an even number (2m) of neighbors of even degree.
Then, since v itself has an odd degree, the addition of v (and the edges incident to it in G) to G', increases the number of vertices of odd degree by (2k + 1) + 1, and decreases the number of vertices of odd degree by 2m. Therefore, the number of vertices of odd degree in G' is changed by 2k + 2 - 2m = 2(k + 1 - m) = 2p, in order to obtain G. Since there was an even number of (2n) vertices of odd degree in G', the number of vertices of odd degree in G is equal to 2(n + p), which is an even number. So P(n + 1) follows in this case.

Case 2.2: v had an even number (2k) of neighbors of odd degree, and an odd number (2m + 1) of neighbors of even degree.
Then, since v itself has an odd degree, the addition of v (and the edges incident to it in G) to G', increases the number of odd vertices by (2k) + 1, and decreases the number of vertices of odd degree by 2m + 1. Therefore, the number of vertices of odd degree in G' is changed by 2k + 1 -2m -1 = 2(k - m) = 2p, in order to obtain G. Since G' had an even number (2n) of vertices of odd degree, therefore, the number of vertices of odd degree in G is equal to 2(n + p), which is an even number. So P(n + 1) follows in this case, as well. This concludes the proof of Case 2.
Case 3: v had s > 0 neighbors, where s is an even number.
Since v had an even number of neighbors, this means that v had an even number (2k) of neighbors of odd degree, and an even number of neighbors (2m) of even degree. Since the degree of v itself is even, the addition of v (and the edges incident to it in G) to G', increases the number of vertices of odd degree by 2k and decreases the number of vertices of odd degree by 2m. This means that the number of vertices of odd degree in G' is changed by 2k - 2m = 2(k - m) = 2p, in order to obtain G. Since G' had an even number (2n) of vertices of odd degree, therefore, the number of vertices of odd degree in G is equal to 2(n + p), which is an even number. Therefore, P(n + 1) follows in this case as well. This concludes the proof of the whole theorem.

This is my proof of the aforementioned theorem. I'd appreciate it if someone can verify the proof.

[stray reef]

seems legit but were you required to do it by induction

[remote island]

No

It just seemed natural to me to do so

[stray reef]

handshake lemma tho

[remote island]

This was only the first part of a problem, the result of which is then used to prove the handshake lemma.

[stray reef]

just to be clear im referring to the formula $\sum_{v \in V} \deg(v) = 2|E|$

[vital dew]

Ann

[stray reef]

which strikes me as almost self-evident

[unborn pasture]

How does one answer a question like this? " I'm thinking of two natural numbers a and b, i reveal that a * b is a prime number and that a^2+b^2 is also a prime number, can you with certainty guess which numbers** a and b** are?"

I would reason like this, if a*b is a prime then it means that either a or b must be 1 since primes are divisible with either 1 or themselves. So we can let either a or b equal 1, then we can try some values for b or a and see if we can' find a value. So if a = 1, then b could be 2 since 2 is the smallest prime, this leads to 1·2 = 2, which is a prime, but also 1^2+2^2=5 which also is a prime. So the only solution is 1 and 2. Does reasoning make sense? Or is there another way of approaching a problem like this?

[wild spade]

You did not prove the unicity of the solution

You have just found one solution

[unborn pasture]

right right

[wild spade]

You have to justify why if b is prime > 2 then b^2+1 cant be prime to have the unicity

[unborn pasture]

oh

how can i show that if b > 2 then it can't be a prime?

[wild spade]

||Look at the parity of b and b^2+1 if b is prime > 2||

[unborn pasture]

im thinking

[wild spade]

Sorry for the spoiler

[unborn pasture]

if b is a odd number, then the result would be a even number which is divisible by 2.

if b is a even number, then a · b is not prime but a^2+b^2 would be a prime

for example b = 5, then 5^2+1 = 26, first statement is true but the second one is not true
b = 6, first statement is false but the second statement is true.
so the only solution is 1 and 2

is this reasoning good? 🙂

[wild spade]

You just need the first sentence to conclude

If b is even b^2+1 is not necesseraly a prime

For instance 8^2+1=65=13.5

[unborn pasture]

Alright, thanks 🙂

[last spire]

Hi, I tried doing this problem and I came up with the following answer:

Let set A_1 be the set of all prime numbers including 1.
Let every subsequent set A_n be the set of the multiples of the nth element in A_1 excluding elements which have appeared in previous sets.

Is it correct? I feel as though it might be a bit wrong or cheat-y--

(P.S.: Sorry if I posted this under the wrong subchannel;;;)

[pale epoch]

should work

they are disjoint by construction, you only need to convince yourself that every set is infinite

and that every natural number appears in one

[last spire]

I see, thank you!

[pale epoch]

you should do this if you think its wrong

not sure why you think its cheat-y

this is more or less the same idea i would've come up with immediately

[last spire]

oh, it just felt weird to just say that one should exclude elements which have already been mentioned in previous ones-- felt as if there was a more-- non-self-referential solution, should I say?

[pale epoch]

oh ok

well, its fine

but it makes it harder maybe to verify that each set is infinite

obviously there are infinitely many multiples of p

but you now also have to show that there are infinitely many multiples of p that arent multiples of some q_1, ..., q_k

[last spire]

yeah-- like in 12 and such

either way, I'm just glad I got a decent answer+

[last spire]

thanks for the tip!

[remote island]

True, but that sum was not used in the proof.

I mean, not explicitly, at least

[stray reef]

yeah but you could've used it. and the proof would've become much less of a hassle that way

[remote island]

Hmm would you please write the overall sketch of the proof idea you have in mind?

[stray reef]

the parity of \sum_{v \in V} deg(v) depends only on how many odd-degree vertices there are

if there are an odd number of such vertices, then the sum is odd; if there are even number of such vertices, then the sum is even

but since the sum is equal to 2|E|, it is even

[remote island]

Fair

[fair hound]

When people say these 2 compound propositions are logically equivalent, do they simply mean they have the same truth value?
E.g.

(¬P ∨ R) ∧ (¬Q ∨ R) =
[Truth value TTTF ]

(P -> R)∧ (Q -> R)
[also has truth value TTTF ]

[remote island]

Yeah

Another way is to say that A <-> B is valid (where A is one of the propositions and B is the other)

That can only be valid if the two propositions get the same truth value all the time

[fair hound]

Thanks
IDK why it took me so long to understand Logical Equivalence.

[remote island]

It's ok, understanding math properly can (and often will) take time, as I am experiencing it too.

But it's a really good feeling when you grasp things or discover things for yourself.

[fair hound]

Yeah, especially when few days ago you couldn't even wrap your head around it.

[remote island]

Theorem: In every tree, there is a unique path between every pair of vertices.
Proof: The proof is by induction on the number of vertices.
Inductive Hypothesis: The inductive hypothesis, P(n), states that in every tree with n vertices, there is a unique path between every pair of vertices.
Base Case: Since trees must be connected and acyclic, then the base case is P(1). The base case is trivially true, since it only consists of one vertex v, which is connected to itself by a unique path of zero length, by definition.
Inductive Step: Assume that P(n) is true for some n > 1. Consider a tree T with n + 1 vertices. Remove a leaf node e from T, along with the edge incident to e, to obtain the tree T'. Since T' has n vertices, then by the inductive hypothesis, there is a unique path between every pair of vertices in T'. Assume that the node adjacent to e in T is d. Now, add node e and edge {d, e} to T', in order to obtain T. The only thing left to show is that there is a unique path between e and every other node in T, since there is a unique path between every other pair of nodes, by the inductive hypothesis. Since d and e are adjacent by a single edge, there is a unique path between d and e. For every other vertex v in T, since there is a unique path between v and d, by the inductive hypothesis, and since there is a unique path between d and e, therefore, there is a unique path between v and e. This concludes the inductive step. Therefore, the theorem follows by induction.

Is this proof of mine correct?

[stray reef]

the last step could be UM ACKSHUALLY'd along the lines of "this shows that there exists a unique path from v to e passing through d, not that there exists a unique path from v to e. why does every path from v to e have to go through d?"

[remote island]

Yeah I agree

Maybe I could write "Since e is only adjacent to d (by the definition of e being a leaf), then the path from any vertex v to e must contain the vertex d."?

And the rest would just follow

To be really detailed, this last claim can also be argued by contradiction. Though I guess the claim itself clear enough and perhaps doesn't need that much detail?

[shadow grove]

"How many 3-digit hexadecimals start with a letter (A-F) or end with a numeral (0-9) (or both)? Explain".

We can divide the Hexidecimal set into three:
H = {0,1,...,9,A,...,F}
N = {0,...,9}
L = {A,..,F}

We then create the two aggregate sets for 3-digit hex starting with a letter and 3-digit hex ending with a numeral:
|3L| = |LXHXH| = 6 * 16^2
|3N| =|H-1XHXN| = 10 * 15^2

In 3N we have to remember that if the first digit is 0 it is insignificant, i.g 052 = 52.

I interpret the question asking us for
|3LU3N| = |3L|+|3N| - |intersection(3L,3N)|

For the sake of writing it easier, I rewrite and rename:
|intersection(3L,3N)| = M.
|3L|+|3N| = 16^2 * 6 + 15 * 16 * 10
|3LU3N| = 16^3 - M

Now M must then be all those 3-digit hexes that start with a letter and end with a digit, so

M = |LXHXN| = 6 * 16 * 10

Meaning
|3LU3N| = 16^2 * 6 + 15 * 16 * 10 - 960

But this is the wrong answer?

[unique abyss]

Looks right to me

What’s it saying the right answer is?

[shadow grove]

Nothing, it just says mine is wrong, lol

[unique abyss]

3136 right?

[shadow grove]

Yeah

[unique abyss]

Maybe the problem is asking for starting with a letter or ending with a numeral but not both

That's typically how the word "or" is used in English

only thing I can think of

unless ofc it explicitly says "or both"

Your logic looks right to me

[shadow grove]

Try reading the question again, if you haven't noticed (or both)

[unique abyss]

Oh so it explicitly says that

I see

I thought the words in parentheses were your annotation to the problem

[shadow grove]

I am also laughing, because this is indeed something I would do. But in this case, it is just copy + paste.

So, my logic still holds right?

[unique abyss]

Yeah it holds

maybe for the ending with the numeral case the number of possibilities is 15 * 16 * 10

15 in the front because we exclude 0. that would be a leading 0

so it would be a 2-digit hex instead of 3

try it with 15 * 16 * 10 for |3N|

[shadow grove]

What?

I doth noteth followeth thine logic

But 151610 + 16^2*6 - 960

[unique abyss]

Suppose I were to ask you for a 3-digit decimal number. And you gave me 056

056 = 56

See what I mean?

[shadow grove]

Oh no

[unique abyss]

I'm applying that same logic to hex

[shadow grove]

056 is different from 56, I am pretty sure

But I could try, I guess

[unique abyss]

Also be careful with how you're using *

You are italicizing a lot of stuff lol

[shadow grove]

2976, right?

[unique abyss]

yes

[shadow grove]

It was not the right answer.

[unique abyss]

Don't think so

[shadow grove]

Bruh, it might just be broken

[unique abyss]

Probably

[shadow grove]

Oh no sh1t you're right

[shadow grove]

Yeah

[unique abyss]

2976 was right?

[shadow grove]

No, just the leading 0

smart observation

[unique abyss]

ah okay

[shadow grove]

wait

No... Nvm

THe other two sets do not contain 0 at the beginning.

I'm gonna be honest, I don't even know how the "divide" symbol works anymore.

But I suppose it is

8/2 * 4

Could you write single words into one message? I am trying to get help with my own question, and this is sending it wayyy back in teh chat.

Which is here: #discrete-math message

Thanks 🙂

[unique abyss]

@shadow grove edit your message btw to make spaces in between the *

it's hard to read

E.g. Here it looks like it is $(1016)^{2}$ while it actually is $10 \cdot 16^{2}$

[vital dew]

ALPH2H

[shadow grove]

Alright done

[meager hare]

Hello, I need help finding the closed form of a sequence.

1,7,15,25,37,51

How would I go about that?

[proper iron]

67

85

105

[meager hare]

yah but closed form is a(sub)n

ex: a(sub)n = n^2+2n

or something like that

[proper iron]

No lol

[meager hare]

what

[proper iron]

a_1=7 not 3

Plug n=1 for your formula

The 3 isn't there

[unique abyss]

He was using that as an example

[meager hare]

what 3

[proper iron]

This is wrong

[meager hare]

yeah my bad, that was an exmaple. I wasn't saying that was the answer

[meager hare]

in the scenario of this question a_1 = 1

[proper iron]

Huh

[meager hare]

the question on my hw does not give me a_0

it just gives me a_1

i think im supposed to use polynomial fitting

[proper iron]

I define things as a_0=1 , a_1=7

And so on

[meager hare]

yah me too

[proper iron]

Cool beans

[meager hare]

but in the question I am being asked. it just gives me 1,7,15,25,37,51 and says a_1 is 1. Find the closed form

ive always had a_0 so im lost 😦

[proper iron]

Honestly there probably should be a 3 in between 1 And 7

Otherwise that would be a super tough problme

[meager hare]

yeah i find it annoying

[unique abyss]

Note that the sequence of differences in between the terms is arithmetic 6, 8, 10, 12...

[meager hare]

I found that the difference is 6,8,10,12

so the second difference is 2,2,2,2

oh lol nice @unique abyss

[proper iron]

a_n=a_n-1+2

Just say that

a_n-a_n-1=2 so it shows difference is 2

But not including the 3 as the 2nd term is probably a mistake

Unless it's a very hard math sequence

[meager hare]

if the 3 was there then the arithmetic sequence wouldn't be there would it ?

[proper iron]

It wouldn't be existing wym?

[unique abyss]

Do you know what that tells you in the context of polynomial fitting?

[meager hare]

I do not

new to polynomial fitting, only learned it in lecture last class

[unique abyss]

It tells you the closed-form formula is quadratic

[meager hare]

oh i remmeber that

an^2+bn+C

[proper iron]

What is this equal to

According to your vlass

Class

[meager hare]

a_n = an^2+bn+C

because it is an arithmetic sequence and I am using polynomial fitting

[proper iron]

1=a+b+C

7=4a+2b+C

15=9a+3b+C

Now you can solve for a_n

[meager hare]

oh i see what you're doing, you're going through n=1, n=2,n=3

[proper iron]

Best approximattion

[meager hare]

im there rn, how do i solve for a_n? that's the tough part

[proper iron]

I knew something was t right when I saw the 3 missing..I was like it's probably going to be some sort of approximated sequence

Ok

To solve for a_n

You have to find a b and C

You have 3 equations and 3 unknows

You can do it I believe you can

[meager hare]

HAHAHA

i ll try my best

[proper iron]

Yes ok goodluck

Last time I felt like someone tried to kick me out of here because I was giving answer jajaja

[meager hare]

usually when I solve equations like this, i have a_0 and that one gives me C

so then all i would have to solve for is A and B

[proper iron]

Ignore the a_0

That's my notation

Let's instead do a_1

For the sake of your classs

[meager hare]

a+b+c = 7

[unique abyss]

Let us know how it goes

[proper iron]

7*

[meager hare]

oops typo

I solved for C in all 3 equations and now

I have hit a wall

there is still A and B in all 3 equations

wtf

[proper iron]

Yes

If you have 3 unknows

You need 3 equations to solve all of them

So you have enough equations

You can do it I know you can your pfp is the probably the strongest in their anime

You should be able to do it with the power of anime

[meager hare]

[Entering flashbacks of all the training I've done]

[proper iron]

You're gonna enter into those flashbacks and more

You got this

https://c.tenor.com/1hdsn62I4tkAAAAM/turtle-cute.gif

[meager hare]

im going to use the augment strat

[proper iron]

Huh

[weary tiger]

p(x)=x^3-6x+10 p(0)=?

okay 10

[weary tiger]

How do I compute $$\sum_{n_1+...+n_k = n} \binom{n}{n_1, ..., n_k}^2$$

[vital dew]

Blitz

[proper iron]

First define n_1,n_2,...n_k ? Do you mean to multiply them?

[little prism]

they are using the multinomial coefficients

[vital dew]

VincentBH

[olive wren]

Not sure there’s a closed form:

https://mathoverflow.net/questions/407305/sum-of-squares-of-multinomial-coefficients

[remote island]

If this does not interrupt the current chat, can I ask for a verification of my solution to a problem?

[olive wren]

Better to ask for forgiveness than permission

Or something like that

[remote island]

Fair 😄

This is my solution to this problem:

(a) Consider two sets L and R, where R is the set of so-called eligible clubs and L is the set of students who are members of those clubs. Define the graph G = (V, E) where V = L U R and E is the set of all edges {u, v} such that u is in set L, v is in set R, and the student represented by vertex u is a member of the club represented by vertex v. Since no two vertices in L are adjacent, and no two vertices in R are adjacent, then the graph G is bipartite by definition. The problem now consists of finding a matching M in G such that every vertex in R is incident to an edge in M.

(b) Since no student is a member of more than 9 clubs, and since $\sum_{v \in L} deg(v) = |E|$, therefore $|E| \leq 9|L|$. Similarly, since for each club to be eligible, that club must have at least 13 members, then $|E| \geq 13|R|$.

[vital dew]

alijfri99

[remote island]

Therefore, $13|R| \leq |E| \leq 9|L|$. It follows that $|L| > |R|$.

[vital dew]

alijfri99

[remote island]

Since there are more members in eligible clubs than there are eligible clubs, therefore, the matching formulated in part (a) exists.

Is this solution correct? Especially, is this much detail enough for part (b)?

I guess that last bit could probably be followed by an inductive argument, not sure if it's necessary though.

[weary tiger]

Oh. Thanks. I've started to think I'm missing something obvious here

[weary tiger]

I think I've found recursive formula for even n and k = 4

[lusty fern]

Hi, I’m taking discrete math for computer science this upcoming semester. Any tips or resources that can help me prepare? A lot of people have told me this is one of the hardest math classes because it’s “different” from typical math

[next bone]

its still best to just practice practice practice. also if your lecturer sucks find a youtuber that works for you and watch their stuff as well, I like TrevTutor on yt

[weary tiger]

weird they say that, usually people find it the easiest of the engineering math courses

[outer rune]

can someone check my answer?

nvm its right

[weary tiger]

Schaum's outlines: discrete math

[silent hinge]

@coral parcel

[coral parcel]

Don't randomly ping people, please.

[silent hinge]

just wanted to say hi

[ember obsidian]

that doesnt justify pinging random ppl

[final cliff]

Discrete Math and its Applications by Kenneth Rosen is a pretty good discrete textbook.

[remote island]

The "Mathematics for Computer Science" course by MIT is also pretty good. I'm currently going through it too and I really like it. You can access their assignments and exams, as well.

[serene marlin]

<@&286206848099549185> looking for a few 1hour private sessions up until my august 13th final, Discrete Maths 1... PM me if any credible tutors are available

[ocean coyote]

I got a different answer

5*4*8*7*26^2=757120

oh wait nvm I see it

it is 26x25

[chilly kayak]

is the author wrong here? I am pretty sure A is the correct option. even his explanation at bottom doesn't make sense.

https://highered.mheducation.com/sites/125967651x/student_view0/self_assessments.html

Negation Of Propositions - Chapter 1

[remote island]

Yeah I think the author is wrong here

Define predicate P(x) as 'x is present today'

The original statement is saying that ~P(Bill) ^ ~P(Rob)

therefore, negating it results in P(Bill) or P(Rob), which is what choice A is saying.

[cerulean cosmos]

Hey so what are the edges and leaves in a tree graph?

This is probably the most silly question

[narrow trench]

The edges are the same thing as in any other graph : links between two vertices

[cerulean cosmos]

So like if it’s A-B-C does this mean there are 2 leaves and 1 edges?

Where A and C are leaves and B is an edge

[narrow trench]

You're mixing up edges and nodes

The edges in bold : A**->B->**C
The nodes in bold : A->B->C (i'll get back to this)

Trees are usually seen as a directed graph meaning that links between two vertices have a direction : every vertex has arrows pointed towards each of its vertices

Like so

As you can see, the root has no arrow pointing to it

[cerulean cosmos]

Yeah

They are the leaves right?

[narrow trench]

no

Leaves are then just the vertices that don't have children

The bottom 4, in the example I gave

(I had to make the graph directed, otherwise you could also go up the tree instead of just down)

Edges : the arrows
Nodes : vertices that have children
Leaves : vertices that don't have children
Root : the vertex that doesn't have a parent

[cerulean cosmos]

So the children start from top?

Because if the bottom four are roots with no parents then are they childrens on top?

[narrow trench]

Why would the bottom four be roots?

[cerulean cosmos]

Wait silly me

I read it wrong

Top is the root

[narrow trench]

Indeed

[cerulean cosmos]

Bottom 4 are the leaves?

[narrow trench]

yeah

(i should mention that parents pointing towards their children is just a convention, and you might see it reversed sometimes)

[cerulean cosmos]

Got it

Can a tree have more than 2 leaves connecting to one parent?

[final cliff]

Yes

A tree with at most two children per any given node is called a binary tree.

But there are other kinds of trees besides binary trees ofc

[cerulean cosmos]

Just to make sure with my understand, is this a tree with 5 edges and 3 leaves?

[cerulean cosmos]

Oh right

[unique abyss]

yes you got it

[cerulean cosmos]

Yay

Also one more q

Is eulerian walk basically drawing the graph with one stroke?

[unique abyss]

That's an intuitive way of thinking about it yeah

[cerulean cosmos]

To find an isomorphism between two graphs. Do they need to have same number of vertices?

[sturdy ivy]

Ummm nice pfp?

[narrow trench]

Yes

A graph isomorphism is just a bijective function between the vertices, with some additional properties

For there to be a bijection between the vertices, they must be equal in number

[opaque delta]

I require assistance

I got a sone

Done *

Need help with c)

[narrow trench]

@quick pebble alright

[hard stone]

isn't it just, any difference in the original array is the sum of differences in the sorted array

therefore the sorted array must also have bounded difference

am I missing something here

[narrow trench]

Bounded by the same number

[hard stone]

yes since the max difference of the sorted array must be smaller than the max difference of the original array

[quick pebble]

And it can go up or down (trying to contribute)

[hard stone]

right, but we care about is the absolute value right

[1,3,2] -> [1,2,3] then you can see that 2-1 + 3-2 = 3-1

[quick pebble]

Discovery process
filtered a Cartesian product of sets with themselves and was showing my grandma and saw that for all sequences, the sorted sequence also obeyed the bounding and went "well shit"

At least now I can look at combinations instead of Cartesian sets, but I won't get all such orderings of a multiset that obey the bounded difference

[hard stone]

thus each difference in the sorted array is bounded by a difference in the original array

and we're done

[vital dew]

Syst3ms

[hard stone]

writing this formally is fairly straightforward, as long as you know about telescoping sums

it's just a matter of using indices and permutations of indices rather than explicit numbers

[quick pebble]

I do not, but is this result noot not worthy because of how simple it looks to prove? NGL a lot of other sequence types get their own term lol

[hard stone]

actually there might be cases I'm not accounting for here

yeah there definitely are

[narrow trench]

It sounds like the kind of problem where it becomes very annoying once you try to write it formally, even though it's plainly obvious intuitively

[hard stone]

oh you can also just use induction

on the size of the array

that handles it easily

[narrow trench]

Oh yeah

If the n+1-th element should be ordered somewhere else, that can only reduce (or leave unchanged) the difference between consecutive numbers

[quick pebble]

A different problem is to find the sequence of a multiset that is bounded to a difference but has a centered sort. So it goes down to a minimum then back up.

So like [1 2 2 3 4 4 5] has a few orderings, but this one is symmetric about center
[4 3 2 1 2 4 5]

Edit: This is more like an algorithm than math so maybe wrong place

OK friends, off to take a shower, but I hope the questions got you interested

[quick pebble]

It is really intuitive, yet I was also incredibly suspicious of my intuition. I thought for sure the differences would want to be spread out.

[plucky island]

Need help with (c) already completed a,b lmk @ me if you want to help ty ty

[plucky island]

I found this online for the same question but I don’t understand it

[unique abyss]

@plucky island @craggy flax Hey guys, I've been playing around with this and I think that I found another solution that can turn the floor function into an inequality which is easier to work with

If $\lfloor \frac{n}{2} \rfloor = b$, Then $ n \geq 2b$

[vital dew]

ALPH2H

[unique abyss]

And if $\lfloor \frac{2n}{3} \rfloor = c$, then $ n \geq \frac{3}{2}c$

[vital dew]

ALPH2H

[unique abyss]

This gives us a lower-bound for n. We’ll use this later on

I’ll pick off from where you guys applied the induction hypothesis

$a_{k+1}>4{\lfloor\frac{k+1}{2}\rfloor}+4\lfloor\frac{2(k+1)}{3}\rfloor+(k+1)$

[vital dew]

ALPH2H

[unique abyss]

Let’s define $\lfloor \frac{k+1}{2} \rfloor$ as p and $\lfloor \frac{2(k+1)}{3} \rfloor$ as q. Let’s rewrite the above with this substitution

[vital dew]

ALPH2H

[unique abyss]

$a_{k+1} > 4p + 4q + (k + 1)$

[vital dew]

ALPH2H

[unique abyss]

Now we know $k+1 \geq 2p$ and $k + 1 \geq \frac{3}{2}q$ because of this.

[vital dew]

ALPH2H

[unique abyss]

We’ll assume that k + 1 is at its absolute lowest

I.e. $k+1 = 2p = \frac{3}{2}q$

[vital dew]

ALPH2H

[unique abyss]

$a_{k+1} > 4p + 4q + (k + 1) = 2(2p) + \frac{8}{3}(\frac{3}{2}q) + (k+1)$

[vital dew]

ALPH2H

[unique abyss]

Now applying this

$a_{k+1} > 4p + 4q + (k + 1) = 2(k+1) + \frac{8}{3}(k+1) + (k+1) = \ \frac{17}{3}(k+1)$

[vital dew]

ALPH2H

[unique abyss]

And: $\frac{17}{3}(k+1) > 4(k+1)$

[vital dew]

ALPH2H

[unique abyss]

Now what about cases where k+1 is not at its absolute lowest

Well if it’s true for the lower-bound of k+1, the inequality should hold for cases where $k+1 > 2p$ and $k+1 = \frac{3}{2}q$

[vital dew]

ALPH2H

[unique abyss]

Or if $k+1 = 2p$ and $k+1 > \frac{3}{2}q$

[vital dew]

ALPH2H

[unique abyss]

Just mapped this out in my head so there may be some mistakes

[plucky island]

Huh yeah this looks great clever change for the floor function

[unique abyss]

Yeah

Not totally sure if this is right though 😂

[unique abyss]

This is pretty hand-wavy

[plucky island]

Yeah I’m not sure I entirely understand the last half and the assumptions but the floor function replacement seems intuitive and clever

Does the fact that k>4 help with anything ?

[unique abyss]

That was used in the base-case/inductive hypothesis step

[unique abyss]

the idea behind the assumptions is that once we get here:
$2(2p) + \frac{8}{3}(\frac{3}{2}q) + (k+1)$

[vital dew]

ALPH2H

[unique abyss]

Oh I can actually bring in @craggy flax 's proof

$k + 1 = 2p = \frac{3}{2}q$ if k+1 is a multiple of 6

[vital dew]

ALPH2H

[plucky island]

Well it’s definitely interesting to see multiple ways

[unique abyss]

Pretty sure you could proceed with a proof by cases

so I proved when $k+1 = 2p = \frac{3}{2}q$

[vital dew]

ALPH2H

[unique abyss]

next you'd do $k+1 > 2p$ and $k+1 = \frac{3}{2}q$

[vital dew]

ALPH2H

[unique abyss]

and then $k+1 = 2p$ and $k+1 > \frac{3}{2}q$

[vital dew]

ALPH2H

[unique abyss]

I don't know if the last case is possbile

this one $k+1 > 2p$ and $k+1 > \frac{3}{2}q$

[vital dew]

ALPH2H

[plucky island]

I don’t believe it is

[craggy flax]

Hi, this is an interesting alternative you have. I like this substitution step you are doing

I have a slight issue tho, maybe you check this

I agree that

$k+1 \geq 2p$

[vital dew]

Social Capital Gainer

[craggy flax]

However my issue is that in the inequality

$a_{k+1}>4{\lfloor\frac{k+1}{2}\rfloor}+4\lfloor\frac{2(k+1)}{3}\rfloor+(k+1)$

[vital dew]

Social Capital Gainer

[craggy flax]

We can only construct lower or equal numbers to the right hand side

Since k+1 is bigger than or equal to 2p, then the right hand side of

$a_{k+1} > 2(k+1) + \frac{8}{3}(k+1) + (k+1)$

[vital dew]

Social Capital Gainer

[craggy flax]

Is potentially bigger than the right hand side of

$a_{k+1} > 4p + 4q + (k + 1)$

[vital dew]

Social Capital Gainer

[craggy flax]

We cannot assume the lowest possible scenario of

$k+1 \geq 2p$

[vital dew]

Social Capital Gainer

[craggy flax]

As we cannot justify that assumption

Instead I will add on a little bit to what you wrote initially

If

,,\lfloor x \rfloor =p

[vital dew]

Social Capital Gainer

[craggy flax]

Then

,,p \leq x<p+1

[vital dew]

Social Capital Gainer

[craggy flax]

We now use the other inequality, the one that lets us construct a smaller number than p

Therefore

,,\left\lfloor \frac{k+1}{2} \right\rfloor =p

[vital dew]

Social Capital Gainer

[craggy flax]

Implies

,,\frac{k+1}{2} < p+1

[vital dew]

Social Capital Gainer

[craggy flax]

Or

,,p>\frac{k+1}{2}-1

[vital dew]

Social Capital Gainer

[craggy flax]

From this point, the proof actually goes in the same way as the second part of what we discussed yesterday

@unique abyss do let me know what you think if you get a chance to look at this, thanks

[unique abyss]

I think what you're saying works yeah

[unique abyss]

My idea was that if we've proven that $4p + 4q + (k+1) > 4(k+1)$ is true in the lowest case, then $2(k+1) + \frac{8}{3}(k+1) + (k+1) > 4p + 4q + (k+1) > 4(k+1)$

[vital dew]

ALPH2H

[unique abyss]

with the $4p + 4q + (k+1)$ in the middle being the low-bound of k+1

[vital dew]

ALPH2H

[unique abyss]

and yes, I agree with this

I think proof by cases could work

#discrete-math message so basically proving these two cases, as I've proved the low-bound case

[unique abyss]

couldn't you also say that if the inequality holds when $p = \frac{k + 1}{2} - 1$ then the inequality holds when $p > \frac{k+1}{2} - 1$

[vital dew]

ALPH2H

[unique abyss]

It holds if p is at an impossible low-bound, so it should hold when p is greater than that for this case

hand-wavy ik 😂

I like your method as well btw

The underpinning idea is that you can write all positive integers $\geq 3$ in the form $6(q) + r$

[vital dew]

ALPH2H

[unique abyss]

and the reason to pick 6 is that it guarantees a integer coefficient for $q$ after going through the fractions and floor

[vital dew]

ALPH2H

[unique abyss]

I can't help but think that there's a simpler way then what both of us proposed as @plucky island said this was an intro course

[plucky island]

For this problem actually the step from 4(7k/6)+(k+1) which works into 4(k+1) it’s only true for k>4 I’ve calculated I think it’s 3.7> makes it > 4(k+1) is thag a problem because we state n>3

[unique abyss]

Yeah

That uses the same principle as what I’m doing

Converting the floor to an inequality

[plucky island]

For the above example actually is it fine that 4(7k-5/6)+(k+1) has to be greater than 4 for it to be > 4(k+1) as we state it is for all integers >3 ? Or because we prove the base case it’s fine?

[unique abyss]

Both

It’s used in the base case

And In the last step

I think another prove or at least some justification should be provided as to why (7k -5 / 6) Is greater than 3/4(K +1)

[serene perch]

For this question, I just need a hint on how to get started on the proof. Since it's a direct proof, I assumed that 0<a<x and 0<b<y but I'm just stuck on what to do after that step

I have a feeling it has to do with some sort of order and multiplication axiom but I don't know how to apply them in this proposition

[stray reef]

you'll need some properties of < or the definition of < given in your class

[serene perch]

would transitivity work in this case or is it a different property that is used?

because here x isnt compared to y thats the problem

[plucky island]

Okay okay

[stray reef]

transitivity alone is not enough

you need to have some property at hand that says how ordering interacts with multiplication

and it really depends on how R was constructed in your class and whether, for example, a < b => a+c < b+c is part of the definition of <, or a theorem

[true bridge]

What is a "set of sequences"? I've seen sequences of sets, sure, but I think I'm confusing myself with sets of sequences. does anyone have an example/explanation?

Is it just a set A={a,b,c,d,...} where a,b,c,d,... are all sequences?

[unique abyss]

yeah 👍

[unique abyss]

When you see “set of sequences” you think in your head “set made up of sequences”

[true bridge]

okay great

ty

[rustic ruin]

I have a question about Coxeter diagrams

can you represent any graph with them or only those that represent vertex figures of uniform polytopes?

[meager hare]

if (n+1)^2 is odd, then n is even. I am trying to prove this directly. for a number to be odd, it can be 2n+1 . for it to be even, it can be 2n.

[next bone]

can an ambiguous grammar G have a regular expression for L(G) - the language derived from the grammar?

im not just copy pasting a hw question in btw, im actually curious, a question is asking me to give a regular expression for L(G) but an earlier question allowed me to discover G was ambiguous

[meager prairie]

just say only odd times odd is odd

then n is even

?

cases: either m is even or odd. m^2 similarly even or odd. their parity is the same.

since (2p+1)^2 = 4p^2+4p+1 = 2(2p^2+2p)+1 = 2q+1 is odd

etc

[elfin marten]

hello

Could anyone consider this statement as a set The collection of ten most worst singers of USA ?

[meager prairie]

isnt this based on opinion?

does that matter

depends on if its an attempt at a gotcha or not i guess

[meager prairie]

if its opinion based its not clearly defined

just like uhh

the 10 coolest numbers

[final cliff]

If your grammar G has only the following productions: S->aS, S->aaS, S->epsilon then L(G)=a^* but G is also ambiguous because there are two different leftmost derivations of the string aa.

[elfin marten]

yes the conditions are not satisfied adjective is miissing??

[meager prairie]

idk wym, i would say it depends on the context of the question

a common thing in proofs/discrete math afaik is asking students whether something is a statement or not

and then opinions are a gotcha since they lack falsifiability

well idk thats not really relevant

[elfin marten]

ok

[meager prairie]

but a sentiment carries

do you see the problem

like the 10 shortest songs

very clear, time doesnt have ambiguity

idk

its not clear how the set is being constructed so its hard to say

[next bone]

oh i see, the grammar they've given is a bit more complex, but its good to know that regular expressions of ambiguous grammars exist, now I just gotta figure it out 😭 cheers for the explanation!

[elfin marten]

Also i believe there are many ways to express a set in set builder form.

For example, {5, 10, 15, 20 } Can be expressed as A ={ x:x is a sequence of addition of 5 and 5 <= x <= 20 }

or A = {x:x = 5n, n ∈ N and 1<=n<=4 }

which is more intuitive and expressive ?

[stray reef]

the latter, but you've got some style issues

taking the x in x = 5n and gluing it to the x: at the beginning looks odd

however, if you replace "sequence of addition" with "multiple" (and fix the issue i mentioned) then both become equally intuitive/expressive ways of talking about the same set

so {x : 5 ≤ x ≤ 20 and x is a multiple of 5}
and {x : x = 5n, where n ∈ N and 1 ≤ n ≤ 4}

[elfin marten]

It's not sequence of addition is multiplication?

?

[stray reef]

can you say that again but with less word salad?

[elfin marten]

okay thanks, i understand your point. And it's appreciatable.

[light heath]

Im having trouble figuring out if a or b are even or odd, can someone give me a tip/hint?

nevermind the question was worded badly

[craggy flax]

@digital latch I think I may have an explanation for that problem you posted a day or so ago

I can post if it might be useful

[digital latch]

Omg yes please

@craggy flax

[craggy flax]

The only workable way I could find is this. This has two parts, the second uses strong induction and I have slight doubts about it which I'll explain after I show you

[digital latch]

In fact i got this in the end of a long proof by induction too

[craggy flax]

Oh ok, can I ask how you did it roughly, just an outline

We may have the same way is what I'm thinking

[digital latch]

oh no I mean that I was on a proof by induction and for it to be true this equality had to be true

[craggy flax]

Ah I see

[digital latch]

,,\displaystyle\sum_{j=0}^{i-1} (-1)^j \binom{i}{j} (n-(j+1))^{i-1} \stackrel{?}{=} (i+1-n)^{i-1}

[vital dew]

Anoma

[craggy flax]

Just out of curiosity, what was that problem

[digital latch]

Just for fun, the probability distribution of the coupon's collector problem

[craggy flax]

Haven't heard of that distribution

[digital latch]

There is this sequence, and the distribution, according to my results, is $$S_{n-1}(k-1) $$

[vital dew]

Anoma

[craggy flax]

Hhmmm, that's interesting, will need to look at it closer tbh. Anyways, I'll show you what I did, and you can judge how you feel about it

So if we evaluate the sum you have stated up to i instead of i-1, the final term will be

,,(-1)^i\binom{i}{i}(n-(i+1))^{i-1}

[vital dew]

Social Capital Gainer

[craggy flax]

Or

,,(-1)^i(-1)^{i-1} (i+1-n)^{i-1}

[vital dew]

Social Capital Gainer

[craggy flax]

Or

,,-(i+1-n)^{i-1}

[vital dew]

Social Capital Gainer

[craggy flax]

Notice that this is the negative of what the sum up to i-1 is supposed to be

Therefore what we want to show is

[digital latch]

Hoooo i see

[craggy flax]

,,\sum_{j=0}^{i} (-1)^j \binom{i}{j} (n-(j+1))^{i-1} \stackrel{?}{=} 0

[vital dew]

Social Capital Gainer

[craggy flax]

And this will imply the result we want

Now using binomial expansion on the bracket in the sum, we get

,,\sum_{j=0}^{i} (-1)^j \binom{i}{j} \sum_{k=0}^{i-1} \binom{i-1}{k} n^{i-1-k} (-(j+1))^k

[vital dew]

Social Capital Gainer

[craggy flax]

Or

,,\sum_{j=0}^{i} (-1)^j \binom{i}{j} \sum_{k=0}^{i-1} \binom{i-1}{k} n^{i-1-k}(-1)^k (j+1)^k

[vital dew]

Social Capital Gainer

[craggy flax]

Now the principle here will be, for this to equal 0 for all n, we need to consider this as a polynomial in n and each of its coefficients need to be 0

To obtain a polynomial in n, we will swap the order of summation

,,\sum_{k=0}^{i-1} (-1)^k \binom{i-1}{k} n^{i-1-k}\left(\sum_{j=0}^{i-1} \binom{i}{j} (-1)^j (j+1)^k\right)

[vital dew]

Social Capital Gainer

[craggy flax]

The coeficient of n is comprised of several pieces

However the only piece which can equal 0 is in the brackets so we will focus on that

Specifically, we need to prove that

,,\sum_{j=0}^{i-1} \binom{i}{j} (-1)^j (j+1)^k =0

[vital dew]

Social Capital Gainer

[digital latch]

I see for the moment, you have very nice little tips that I didn't have at all, I'm learning a lot thank you

[craggy flax]

For all k that are in the range 0<=k<=i-1

No problem at all! Glad it's useful

So to prove this we will need stong induction on k

However, in doing so, the upper limit of the sum advances by 1

Since k is limited by he value of i

Still not sure how to feel about this but here it is

Begin with the k=0 case

We need to prove that

,,\sum_{j=0}^{i-1} \binom{i}{j} (-1)^j =0

[vital dew]

Social Capital Gainer

[craggy flax]

For all i

This is fairly easy, consider the binomial expansion of

,,(1-1)^i

[vital dew]

Social Capital Gainer

[craggy flax]

That is exactly that sum

[digital latch]

Yes I see that it's almost trivial

[craggy flax]

And it is clearly equal to 0 and true for all i

Now we will consider the case for K and prove K+1, but we will assume the K case to be true for all i just as the K=0 case

We will prove these summed up to i, but let's briefly consider the sum up to i-1

Sorry, I have made a mistake above

I forgot to swap the upper limits on the sums

We want to prove

,,\sum_{j=0}^{i} \binom{i}{j} (-1)^j (j+1)^k

[vital dew]

Social Capital Gainer

[craggy flax]

Is equal to 0

(Sorry for the edits)

[digital latch]

as long as i understand everything is fine

[craggy flax]

Since we have assumed this for all i, consider the sum up to i-1

,,\sum_{j=0}^{i-1} \binom{i}{j} (-1)^j (j+1)^k=0

[vital dew]

Social Capital Gainer

[craggy flax]

Writing the binomial coefficient in full

,,\sum_{j=0}^{i-1} \frac{(i-1)!}{j!(i-1-j)!} (-1)^j (j+1)^k=0

[vital dew]

Social Capital Gainer

[craggy flax]

That should be an i-1 in the binomial above

Not i

Because we only go up to i-1 in the sum

[digital latch]

Yes ok

[craggy flax]

Multiply both sides by i

,,\sum_{j=0}^{i-1} \frac{i!}{j!(i-1-j)!} (-1)^j (j+1)^k=0

[vital dew]

Social Capital Gainer

[craggy flax]

Also

,,\sum_{j=0}^{i-1} \frac{i!}{(j+1)!(i-1-j)!} (-1)^j (j+1)^{k+1}=0

[vital dew]

Social Capital Gainer

[craggy flax]

I put in an extra (j+1) on the top and divided it off again so that I don't change anything

The division by j+1 was put with j! to make (j+1)!

Is that ok?

[digital latch]

Yes it's ok, so we have nCr(i, j+1)

[craggy flax]

Yep

Writing that

,,\sum_{j=0}^{i-1} \binom{i}{j+1} (-1)^j (j+1)^{k+1}=0

[vital dew]

Social Capital Gainer

[craggy flax]

Now we make the substitution j'=j+1

Multiply both sides by -1 first

,,\sum_{j=0}^{i-1} \binom{i}{j+1} (-1)^{j+1} (j+1)^{k+1}=0

[vital dew]

Social Capital Gainer

[craggy flax]

So using the sub

,,\sum_{j'=1}^{i} \binom{i}{j'} (-1)^{j'} j'^{k+1}=0

[vital dew]

Social Capital Gainer

[craggy flax]

Is that ok?

[digital latch]

Yes

[craggy flax]

So if we start the sum at j'=0, we don't change anything

Since that term wil be 0

,,\sum_{j'=0}^{i} \binom{i}{j'} (-1)^{j'} j'^{k+1}=0

[vital dew]

Social Capital Gainer

[craggy flax]

But j' is just a dummy summation variable, so I can relabel it back to j

[digital latch]

I've just never seen strong induction before I think that's what I was missing so I'll probably re-read all of this later to fully understand everything, but everything that is calculus it's fine

[craggy flax]

,,\sum_{j=0}^{i} \binom{i}{j} (-1)^{j} j^{k+1}=0

[vital dew]

Social Capital Gainer

[craggy flax]

Strong induction just means you assume all cases upto and including k are true instead of just the k case

So you can use all of them

As we are about to do

[digital latch]

Ok i think i see

[craggy flax]

So because we assume all cases up to and including k are true, then in addition to the above sum

I have all of these to use

,,\sum_{j=0}^{i} \binom{i}{j} (-1)^{j} j^{l}=0

[vital dew]

Social Capital Gainer

[craggy flax]

Where L can go from 0 to k+1

This is all still just out of the K case and previous

[digital latch]

Ok ?

[craggy flax]

Now multiply the above like this

,,\sum_{j=0}^{i} \binom{i}{j} (-1)^{j} \binom{k+1}{l} j^{l} 1^{k+1-l} =0

[vital dew]

Social Capital Gainer

[craggy flax]

I can do that because it is equal to 0 and the pieces I added do not depend on j

[digital latch]

OOOh

Ok ok

[craggy flax]

Now remember that I have lots of those equations, L can go from 0 to k+1

I will now add them all up

,,\sum_{l=0}^{k+1}\sum_{j=0}^{i} \binom{i}{j} (-1)^{j} \binom{k+1}{l} j^{l} 1^{k+1-l} =0

[digital latch]

The goal is always to show that?

,,\sum_{j=0}^{i} \binom{i}{j} (-1)^j (j+1)^k

[vital dew]

Anoma

[digital latch]

equal 0

[vital dew]

Social Capital Gainer

[craggy flax]

Yep, we are just about to

Now rearrange the sums a bit

,,\sum_{j=0}^{i} \binom{i}{j} (-1)^{j} \sum_{l=0}^{k+1}\binom{k+1}{l} j^{l} 1^{k+1-l} =0

[vital dew]

Social Capital Gainer

[craggy flax]

Notice that the second sum is just (j+1)^(k+1)

,,\sum_{j=0}^{i} \binom{i}{j} (-1)^{j} (j+1)^{k+1}=0

[vital dew]

Social Capital Gainer

[craggy flax]

Which is just what we wanted to show

And thats it

[digital latch]

I learned a lot thank you very much

[craggy flax]

No problem at all, I hope it is actually right

I'm 85% confident in it

[digital latch]

I will still have to read again to fully understand the goal with the strong induction (and check if this is right), i tried a a lot of things and each time i was stuck after using binomial expansion in the sum because I didn't think about induction at all

[craggy flax]

Oke sure no problem

I mean I tried a bunch of other tricks, and honestly there might be an easier way but I can't spot it atm

I definitely think you need to go to the first part tho, just because of how neatly it fits in

But proving the second part, who knows there might be another

Way

Using some polynomial maybe with specifically chosen roots, I dunno

By first part I mean

,,\sum_{j=0}^{i} (-1)^j \binom{i}{j} (n-(j+1))^{i-1} \stackrel{?}{=} 0

[vital dew]

Social Capital Gainer

[digital latch]

Ok yes the goal is always to find the zero polynomial

[craggy flax]

Something like that I guess

But yeah, that's all I've got really

Thanks for posting that problem, it was very interesting

[craggy flax]

Btw, let me know if you would like me to elaborate on anything

I was a bit quick with how I brought L in I feel

[digital latch]

I'm going to sleep now but as soon as I work on it again I won't hesitate !

[craggy flax]

Ok, no problem, good night too!

[signal goblet]

For 2b, are all of the following valid answers:

• aa
• bbaa
• (ab)*
• (bb)*
• aa(ba)*bbab
• (aa(ab)*)*

[stray reef]

definitely not

those regexes generate SUBSETS of L2, not L2 itself

[signal goblet]

Yep, okay, thought so. Would ((ab)|(ba)|(aa)|(bb))* be a valid answer then?

With the extensional definition being something like: {E (empty str), ab, ba, aa, bb, abba, abaa, abbb, baab, baba, baaa, babb, aaab, aaba, aaaa, aabb, bbab, bbba, bbaa, bbbb, ...}

[stray reef]

yes that seems ok now

or maybe

( (a|b)(a|b) )*

[signal goblet]

Ooh yep nice, that's much more concise

Thanks heaps :D

[viral nebula]

theyre not polynomials, but you have to show that the zeroes of these exponential functions are the integers:

[digital latch]

ok so there is no way to have some sort of telescopic sum, everything has to be zero ?

[viral nebula]

umm.. i dont know about that, i just found it interesting that the zeroes of these polynomial-likes are integers :p

[viral nebula]

this is what i don't understand. how do we know that THIS sum is zero? it seems different than what we assume to be zero from induction..

ahh there is an edit later, i didnt see

[elfin marten]

What could be the roster form of this expression A = { x:x is an integer, -1/2 <x<9/2 }

[stray reef]

well, what are the integers which fall between -1/2 and 9/2 on the number line?

[unreal stump]

Is there a good reason to ever use master theorem? Like I feel like I would rather unravel the reccurence and find the solution that way instead of memorizing a weird and unintuitive list of conditions.

[unique abyss]

For simple recurrences, unraveling the recurrence may be all you need, but as they get more complex, the master theorem provides a easy to apply formula

Consider a problem with 10 subproblems

that would take some time to unravel

ultimately, it is a generalization for many different common recurrences and generalizations are always of interest in mathematics

[unreal stump]

Does master theorem even work in that case

I thought master theorem became useless as you soon as you have more than one subproblem

[unique abyss]

Yes it does

The requirement is that the number of sub-problems remains constant

[unreal stump]

Can you give an example of what you mean?

[unique abyss]

Take Merge sort for instance

It divides an array of size n into two arrays of size $\frac{n}{2}$ and then proceeds with recursive calls on both of those smaller arrays. Hence it has two sub-problems

[vital dew]

ALPH2H

[unreal stump]

Well I can solve the merge sort reccurence without master theorem pretty easily

[unique abyss]

Yeah You can solve it with master theorem easily as well

[unreal stump]

T(n)=2*T(n/2)+\theta(n)
So T(n)=theta(n+2*(n/2)+...2^k(n/2^k))=theta(n log n)

Well handwaving a bit but it is not to fill in the details at all

[stray reef]

it's theta, not thetha

unleth you have a lithp

[unreal stump]

If I were to use master theorem,I have to look up the weird conditions think about them for a couple minutes

And then somehow convince myself that is better than what I just did here

[unique abyss]

How about maximum sub array problem

[unreal stump]

Well there's a O(n) algorithm so why even bother with D&C

[unique abyss]

Which conditions are weird?

[unreal stump]

Tell me you think this is not weird

I just don't see the point of memorizing a bunch of results when the results can be derived very easily

[unique abyss]

Yeah you can use Kadane’s but it’s nontrivial (most people are not able to come up with it themselves)

And my example is just to illustrate a case where it may be useful

[unreal stump]

Ok so we are going with
T(n)=2T(n/2)+(n/2)?

[unique abyss]

You’re right that the results can be derived easily for these problems we are discussing

But that doesn’t mean that manual unraveling will always work well

[unreal stump]

Give me a problem where it doesn't work well

And master theorem is better

[unique abyss]

Consider the case I presented already

10 sub problems

[unreal stump]

Well what does that look like

[unique abyss]

Each with say size 1/1000

[unreal stump]

So T(n)=1000T(n/1000)+f(n)?

[unique abyss]

No the a term will be 10

[unreal stump]

T(n)=10T(n/1000)+f(n)?

[unique abyss]

Now try to manually unravel

[unreal stump]

Well you get
f(n)+10 f(n/1000) + 100 f(n/1000^2)...

Which doesn't seem very different from the cases we did earlier

Just substitute a f,bound by a appropriate function and you have your thetha or O bound

[unique abyss]

This answer is a series

Which is typically not useful

It’s like saying the Sieve of Erasthosnes time complexity is O(sum of reciprocal of the primes * n)

Sum of reciprocal of the primes diverges

But it grows on the order log(log(n))

Hence the time complexity is O(n * log(log(n)))

[unique abyss]

In this form, the answer has less meaning

An even better example would when the subproblems have different sizes (technically you’d need Akra-bazzi) but much of the master theorem is included in Akra-Bazzi

[digital latch]

I found the answer here https://math.stackexchange.com/questions/4247900/prove-the-roots-of-these-exponential-functions-are-integers

[limber thorn]

I am having trouble understanding this answer

if I plug f(g)(x)

I get x2 + 2x + 4

I must be missing something weird here

[sharp field]

that's incorrect, $f(g(x)) = (x+2)^2 + 1 = x^2 + 4x + 4 + 1 = x^2 + 4x + 5$

[vital dew]

Transparent_Elemental

[limber thorn]

man my algebra is messed up...

what is really confusing me is the g(f(x)) - because if I plugin X^2 +1 for X then I get: (X^2+1)+2 right? - so I am just getting X^2+3 - like how are they doing the g(f(x)) ?

[sharp field]

yes, and probably should move it to like #prealg-and-algebra

[limber thorn]

Well these are the only ones like this, the entire course is discrete math but the last math course I did was Cal over a decade ago, so I remember most things but a couple of these kinda trip me up a little bit. like I realized my mistake immediately, but on the g(f(x)) I am wondering what they're actually doing because plugging in f(x) in place of g is not seeming to getting me there

[limber thorn]

nvm the answer is zero so I had it right, the qeustion is just set up really stupid

[rustic zealot]

Im really lost with this one

how can I achieve that

[olive wren]

So notice that if you have a sequence of length $n-1$, you can add black or white to it to get to a valid sequence of length n. (So to get a sequence of length n which doesn’t end in orange, you have $2a_{n-1}$ choices)

To get a sequence of length n which ends in orange, the color before it must not be orange so you take any sequence of length $n-2$, add a black or white square and and then add an orange square. So there are $2a_{n-2}$ choices for this.
So you should have:
[ a_n = 2a_{n-1} + 2a_{n-2} ]

And notice:
\begin{align*}
a_0&=1 & \text{(the empty sequence)} \
a_1&=3 \
a_2&=8 \
a_3&=3^3 - 4 - 1 = 22 & \text{($3^3$ total sequences, then 4 sequences with two orange and 1 with three consecutive orange)}
\end{align*}

[rustic zealot]

Thank you so much ! I understand better now

[olive wren]

[slender obsidian]

does anybody have any idea where I should start? This is my second time taking discrete mathematics and it is still not making any sense

[ember obsidian]

hint: sum of rationals is rational

[slender obsidian]

so, using contrapositive, I will Assume x-y is rational and prove that x is rational?

[ember obsidian]

yes

[slender obsidian]

oh ok. I finally got it by thinking of x-y as x+(-y)!

I am also having trouble trying to prove by induction that (1 + x)^n ≥ 1 + nx. I end up trying to show that (1 +k+1)^j+1 ≥ 1 +(j+1)(k+1) and I have no idea what to do from there

[vale cairn]

Supposing (1+x)^n >= 1+nx, you need to show (1+x)^(n+1) >= 1 + (n+1)x. It seems you've inducted on x (which needn't be an integer!) instead of just letting it be an arbitrary real >= -1

[olive wraith]

what is this statement

what we called them

[wide vine]

👀 what is that notation?

is this some project stuff liike and and or?

[wide vine]

https://math.stackexchange.com/questions/4299976/what-does-bigwedge-bigwedge-bigvee-mean-in-discrete-mathematics?rq=1

[ember obsidian]

'ands' & 'ors' of propositions

cc @olive wraith

more precisely 'ands' of 'ands' of 'ors' of propositions

[wide vine]

I noticed that but never seen it like a sum or product type thnig

where you have some sort "bounds"

[ember obsidian]

ok so u know 'and' & 'or' associate

so u can define 'and' & 'or' of a collection of statements

[final cliff]

People sometimes do $\bigvee x P(x)$ instead of $\exists x P(x)$, it's kinda old and not common any more.

[vital dew]

DootDooter

[ember obsidian]

so like $\bigvee_{i=1}^3p(i)$ instead of $p(1)\lor p(2)\lor p(3)$

[stray reef]

\bigvee

[vital dew]

RokettoJanpu

[ember obsidian]

same for 'and'

[final cliff]

Because if you had a finite domain like {1,2,3}, then for some x, P(x) is equivalent to P(1)vP(2)vP(3).

Conjunction and forall has a similar relationship.

But when your domain of discourse is not finite I think some things don't work right?

Idk like infinite conjunctions/disjunctions aren't really wffs in most logics I think?

[wide vine]

Yea I see what it means not but never actually seen it.

neat

[ember obsidian]

FOL doesnt allow infinite formulas, in particular infinite conjunctions/disjunctions

[final cliff]

Yah I said that lol

Also, kinda convenient sometimes to view things this way because often your quantifier laws act like your normal propositional formula laws.

Like quantifier negation ends up looking very similar to demorgans law from this pov

Like, if $D={1,2,3}$, then $\lnot(\exists x \in D)P(x) \iff \lnot\bigvee_{x\in D} P(x) \iff \bigwedge_{x\in D} \lnot P(x) \iff (\forall x \in D)\lnot P(x)$ or something.

[vital dew]

DootDooter

[raw fulcrum]

hello, sorry if it's not the right channel, I had struggle finding the correct theme for that question:

I'd like to consider a collection of equi-distributed points in the plane. To fix ideas, we can consider the collection of all those points that are corners of squares of side-length 1/n, paving the plane. (so I pave the plane with such small squares, and I check the corners: that's my collection)

if I write $c(S)$ the number of points in my collection intersecting a shape $S$, it is roughly clear to me that for all translation vector $t$ and for all scaling parameter $\alpha$, I'll get $\lim c(\alpha S + t)/c(S) = \alpha^2$, where $S$ is any open square and where the limit is taken as the equi-distance between my points is getting smaller (say $n\to\infty$ in the initial construction)

I'd like to get an elementary proof of the fact that such an asymptotic remains correct for any affine transform: $\lim c(L S + t)/c(S) = |\textrm{det}(L)|$ .

While I find the result quite trivial intuitively, I cann't really get my head around how to formalise it. If possible I don't want to use any kind of integral, unless it can be explicitly written as a series (I'm looking for a proof based on geometric/summation arguments instead of an entire ergodicity theory)

I don't know if anyone could give some clue?

[vital dew]

Expert Symbiont

[signal goblet]

Anyone know a grammar that can produce this language? It's been a long day and I'm not getting anywhere with this question, as all the grammars I produce have slight problems.

NOTE: The notation na(w) is read as "the number of b's in string w." So, the specification is that there are strictly more a's than b's in any string, w, in that language.

[unborn pasture]

How do i prove this statement?
All whole numbers greater than 1, which are not divisible by 2 or 3 are primes.

I tried to break it down into two different cases, case 1: k is even and case 2: k is odd.
case 1: k is even, then it means that 2 divides k, which means k is not a prime.

case 2: k is odd, then we can represent k as 2m + 1, m is not a multiple of 2 or 3 which would mean that k must be a prime. But i don't know if case 2 makes any sense?

[weary tiger]

well for one it's wrong
since 49 exists, is not divisible by both
and is not prime (7*7)
other primes than 2 and 3 exist and their very existence disproves this
sorry if I came off as harsh btw

[unborn pasture]

its not harsh at all 🙂

and of course i forgot you can just use a number and disprove the statement. oufff

[weary tiger]

lol
happens

[unborn pasture]

Thank you for the help!

[weary tiger]

np

[radiant bough]

@stoic cedar are you sure thats even true

The equation you posted

Step 1 to proving something is to make sure it’s true

[vale cairn]

it's gone to competition maff

[final cliff]

Hint: Try generating the language of all strings with the same number of a's and b's first then use this cfg to produce the grammar for the language you want. To produce this new language every production that emits an a must also emit a b.

Preferably you would emit your a and b at the same time.

Notice ab is one such string. So, consider the derivation S->ab

We could have also emitted _ab, a_b, ab_ and so on where _ represents strings containing equal numbers of a's and b's.

Can you generalize this sort of reasoning to build your grammar for this new language?

Now imagine you have this new grammar in hand. Notice if we restrict your given language to the language of all strings with exactly one more a than b there are only the following cases: _a, _a_, a_.

[chilly dew]

I really don't understand what this hint is trying to say. Would anyone be able to help?

[little prism]

consider (x+1)^n, use binomial theorem, differentiate. something like that

[vale cairn]

I wonder if there's a good combinatorical interpretation for this tbh, think there is

[chilly dew]

i think if possible, staying away from combinatorics is preferable

[little prism]

well sometimes combinatorial proofs can be easier

[chilly dew]

I'm sure that's true, but personally i've found it difficult to make rigorous historically

[little prism]

yeah that's true

[vale cairn]

Actually yes it's very cute, ||what's the average size of a subset of {1,...,n}? Clearly it's n/2, but you can also find the probability it has size k and weight it by the size||

[vale cairn]

But the above hint is how to do it analytically sure

[little prism]

ah yeah that's actually a very nice combinatorial proof

it's a good idea to be able to do both. sometimes just bashing through the calculations is easier, but other times a combinatorial proof is easier

[chilly dew]

why would be consider (x+1)^n?

[little prism]

because I think that works

don't wanna go through all details but I think it does

have you seen the proof that sum choose(n, k) = 2^n using binomial theorem on (1+1)^n ?

[chilly dew]

yep

i don't know how that gets us closer to the exercise though

[vital dew]

potato

potato

[chilly dew]

if we run the sum from k=1 to n, it is equal to running the sum from k=0 to n

idk how useful that observation is

oh wait

another idea

[vale cairn]

Basically you can rewrite the sum in another way

[chilly dew]

for k > 1, the sum is equal to k(x+1)^n

right?

[little prism]

no

what do you get when you use the binomial theorem on (x+1)^n

[chilly dew]

$\sum_{k=0}^{n} {n\choose k} x^k$

[vital dew]

swifteeee

[little prism]

yes

what do you get if you differentiate that

[chilly dew]

$\sum_{k=0}^{n} {n\choose k} kx^{k-1}$

?

[vital dew]

swifteeee

[little prism]

yes

and what do you get if you set x=1 ?

[chilly dew]

$\sum_{k=0}^{n} {n\choose k} k$

[vital dew]

swifteeee

[little prism]

ok so that's the LHS

[chilly dew]

so we do the same to RHS?

[little prism]

now lets start again at (x+1)^n, but this time differentiate immediately

[chilly dew]

i dont understand partial differentiation but im guessing it'll be n(x+1)^n-1

setting x =1

[little prism]

partial differentiation? that's just chain rule

but yes, set x=1 and we get?

[chilly dew]

n *2^{n-1}

,w d/dx (x+1)^n

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by swifteeee#9841

[chilly dew]

well either way, thank you so much Dena

just one thing

i still don't understand the motivation for (x+1)^n

is it taking the anti-derivative of n * 2^(n-1) and generalising it for any x?

[wide vine]

,w binomial expansion

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Brandon7716#6524

[little prism]

no

you just notice that you have these factors k on the LHS and n on the RHS

factors like these often come from differentiating powers x^k and x^n

so we kind of want to use that

hmm I'm actually not sure how exactly to motivate that we take (x+1)^n. just seems very natural to me

because using binomial theorem we get exactly what we want on the LHS

[chilly dew]

and then we just apply that to RHS and we get the starting point of (x+1)^n

which is weird to me because it seems to be supposing our conclusion first, then finding a way of getting there second

but if it works, and it's fine logic. i might have to start doing it myself

[little prism]

well yeah sometimes you start where you want and then go backwards

and then when you present the proof you start at the correct start and work forwards

difference between finding a proof and writing it down

[chilly dew]

i was super interested in philosophy before math so my intuition tells me that working backwards from the conclusion is evil

[little prism]

it depends on how you do it

[chilly dew]

or trying to justify your conclusion ad hoc

[little prism]

you need to check that all your arguments hold in the correct direction

but especially for stuff like rewriting equations etc it's often easier to start at the end

[rose wing]

Hello, This is a MIT learning material graph theory matching problem. The mating ritual is on 1:05.

Why he could come up with "girl's favorite tomorrow will be at lease as desirable to her as today's "? but boy's list of girl is getting worse day by day?

I guess the "favorite" boy from the list of a girl would be married in some cycle so the girl will lose her favorite too. But the professor said "the rank of a girl's is weakly increasing".

Thank you

https://www.youtube.com/watch?v=6vgHIImFwHo&list=PLUl4u3cNGP60UlabZBeeqOuoLuj_KNphQ&index=63

[chilly dew]

yeah idk it just pains me haha

[little prism]

don't consider it as proving anything yet

at that point you are just looking for an idea for a proof

[chilly dew]

hm. maybe

[little prism]

the boy that the girl didn't reject will try again the next day. so the girl will have this boy that was her favourite so far and other boys that might be even better

[rose wing]

oh, I see. so that lemma is just based on boy only chase 1 girl at a time. If the game setting is different then the girl might also lose her suitor too isn't it.

[little prism]

yes

[coral parcel]

Is that the stable marriage theorem?

[serene marlin]

for this question part e is it even possible?

i dont see a combination that isnt transitive

while still not being symetric

[vale cairn]

Yeah it is possible

[fresh pawn]

isn't that just called a "total order"?

[ember obsidian]

if its hard to see, try to list all the relations on A

theres only 16

[serene marlin]

we havent learned so idk

ok let me try

[vale cairn]

Strict orders are transitive

[fresh pawn]

Me too, but I always thought working backwards was still okay, I just thought it was highly unintuitive.

[fresh pawn]

Welp

is there a name for a relation that is irreflexive, asymmetric, and not transitive?

[serene marlin]

ok wht the frick is it

i wrote out every combination

and i dont see it

[woeful pulsar]

let's say you have a set A, is the set {A} a partition of A?

I feel like it should be

[stray reef]

it is, trivially

[woeful pulsar]

so it's called "the trivial partition"?

[stray reef]

dunno if that name is actually in use

[unborn pasture]

You can re-write a = b mod m as m | a - b, is it allowed to add/subtract from m |a - b?

For example if i want to transform m | a -b to m + b | a, is this allowed?

[stray reef]

no

a | b does not imply a+x | b+x generally

otherwise you could prove that 5 is even

[unborn pasture]

Oh okay, thats good to know

I assumed you were allowed to add and subtract from it.

[coral parcel]

It will help you if you don't think in terms of "is it allowed?", but "does it work?"

Trying some examples will quickly show you that it doesn't work.

For example, 3 | 9. If we write 9 as 10-1, we have 3 | (10-1), but do we also have (3+1) | 10? No.

[stray reef]

i kind of already suggested something like that

albeit indirectly and only as the goal

[unborn pasture]

that's a another approach. I was trying to solve this " we have a = b mod m n, do we also have a = b mod m & a = b mod n", in the solution they solve it like this a = b + (k *m)n, i assumed maybe you should add them together and let like a equal k or something. Ig they using the Chinese rest theorem ?

[stray reef]

no

chinese remainder theorem is the converse of that

a = b mod mn means a - b is divisible by mn, which obviously implies it is divisible by m and by n

[unborn pasture]

but where does a = b + (k*m)n come from?

I understand that a = b mod mn => a = b mod m & a = b mod n, but i don't understand the solution

[coral parcel]

Do you understand that "a = b mod mn" means "there is some k such that a = b + kmn"?

[unborn pasture]

aha so that if we add b to kmn we get a