discrete-math

[meager prairie]

idk about simpler, but no mod

no need to delet 😄

[marble pivot]

Wait I was thinking

[meager prairie]

if you really dont believe that you could show b < a instead

[marble pivot]

Even numbers can be split up into two columns like this

[meager prairie]

why do you feel interested in this proof specifically?

just curious

[marble pivot]

Well

It’s because it’s so easy to understand

[meager prairie]

its reminding me of abstract algebra

[marble pivot]

But I want a short and elegant way to prove it without being like “let a = 2n modular arithmetic wlog dadada”

[meager prairie]

For two consecutive integers, let a be the even integer. As a|b implies 2a|2b, we have that 4|a.

i think theres an interesting under part to it well at least to me

[marble pivot]

Yeah

No I mean like

[meager prairie]

because its hiding the idea that integers just tick along like

odd even odd even

[marble pivot]

There’s an interesting art of these quick little proofs, to make it as simple and understandable as possible

[meager prairie]

its reminding me of Z2

[marble pivot]

https://math.stackexchange.com/questions/855/for-any-prime-p-3-why-is-p2-1-always-divisible-by-24

I was inspired by this top answer

It’s amazing how there’s proofs of these NT things that don’t actually need much language

[meager prairie]

i think its funny how quickly you can develop intuition for it

[marble pivot]

Yeah haha

[meager prairie]

idk if its just bc its so elementary or whatever

if you havent check out abstract algebra you should

if youre into this stuff

[marble pivot]

So I was like “I wonder if I can make a quick little proof of this without much difficult language”

Yeah I have

But abstract algebra is kinda reliant on this strict language, isn’t it

[meager prairie]

idk

in some ways yea

in other ways no

im obviously far from any kind of expert on it

[marble pivot]

O rly

Wait

What’s an example of an “elementary” abstract algebra type proof

[meager prairie]

[marble pivot]

Cause everything I’ve seen is like “let a and b be elements of the multiplicative group blah blah”

[meager prairie]

hmm

[marble pivot]

Maybe I’m stuck on the intro stuff that is purposefully rigorous tho

[meager prairie]

idk lagrange theorem is kind of cool

but it takes a tiny amount of language

say were on some set {0,1,2,3}

lets work with addition mod 4

so we add the numbers together, then take the mod 4

[marble pivot]

Ye

[meager prairie]

the order of some number in that set is the number of times we have to operate it by itself to get back to 0

so the order of 0 is 1

the order of 2 is 2

(since 2+2=4==0)

can you tell what 1 and 3 are?

well i guess i could stop there

the proof is less* interesting than the theorem

The theorem says that the order of any element of a group is a divisor of the number of unique elements

[marble pivot]

Order of 1 is 3, and order of 3 is 4?

[meager prairie]

order of 1 is 4

[marble pivot]

Oh that’s right

Wait

[meager prairie]

1+1+1+1

[marble pivot]

1+1+1+1+1?

Yeah

[meager prairie]

well were starting from like

beginning with 1 is doing nothing

think exponent notation

but for addition

so thats cool, right? i mean it is to me

[marble pivot]

Ok u mean order of x is the number a such that x+x+x… (a times) = 1

[meager prairie]

yea

[marble pivot]

I see

[meager prairie]

i mean you have things like uhh

[marble pivot]

Oh wait what

[meager prairie]

notice the orders

we have 4 elements

[marble pivot]

Yeah that’s an interesting pattern for sure

[meager prairie]

1 of 1

1 of 2

[marble pivot]

Cool that it extends to any group

[meager prairie]

so get this

something being order 2 means its its own inverse right

sorta like how 1/5 and 5 are multiplicative inverses

not in any group but just in general

but some things can be their own inverses in certain groups

like 2 is its own inverse in Z4

but if you pick something of prime order (bigger than 2) under addition mod n

youll have no self-inverses!

[marble pivot]

Yeah

[meager prairie]

and actually

[marble pivot]

x*x = 1 means it’s its own inverse

[meager prairie]

if you start with any element

in a prime order group

and just start operating it with itself

until you get back to itself

youll have hit every single other element in the process

no matter which element you pick to start

[marble pivot]

Ah

[meager prairie]

i think its cool

it reminds me of harmonics

[marble pivot]

So really the map a -> ax performs a permutation of the elements

[meager prairie]

well permutation groups are their whole own thing sort of

again far from a expert

[coral raven]

oh yeah? oh yeah? what about the identity? boom, destroyed with facts and logic

[meager prairie]

the FIT is one of the collest math things ive seen for a long time

[marble pivot]

😦

[meager prairie]

no boggy logic

[marble pivot]

Fit?

[meager prairie]

big ideas

[marble pivot]

First isomorphism theorem

[meager prairie]

ye 😄

it takes a lil work to get to but its very pretty

[coral raven]

not heard it abbreviated like that before

[meager prairie]

well isomorphisms on their own are pretty cool

i was gonna mention when you were doing your proof of the 0 and 2 thing at the beginning

[marble pivot]

Yeah it kinda makes intuitive sense since the kernel of phi is the set of all elements that map to 0, and in the quotient you’re “setting” those elements to 0

[meager prairie]

that Z2 is isomorphic to Z

i think

idk im very tired

so grain of salt

[marble pivot]

Ah

Yeah

I remember this

It’s so cool

[meager prairie]

wish i wasnt so tired

[marble pivot]

Just skip the stuff before finite support stuff

[meager prairie]

why is Q+ <2>+<3>...

[marble pivot]

Q+ is the positive rationals

[meager prairie]

under multiplication

[marble pivot]

Yes

[meager prairie]

oh

sorry i cant understate how tired i am 😄

[marble pivot]

Just read the 2^a 3^a stuff and on

[meager prairie]

ill look tomorrow

im done

lol

im gonna go to bed

[marble pivot]

Lol ok

[meager prairie]

looks cool tho

[marble pivot]

Ye it’s a direct (!) proof that sqrt 2 is irrational

[gusty musk]

I understand that I'm supposed to sub each x with a y, but the 1 <= x <= 4 is tripping me up and Im not sure how to proceed

[proven silo]

Wdym?

[gusty musk]

like normally Ive been given problems where each is is given their own value like x1 >=4 , x2 >= 5, etc.

[proven silo]

You have the same here? It is saying 1<=x_1<=4 and 1<=x_2<=4… 1<=x_6<=4

[weary tiger]

how to prove intersecting family of size k has at most size n-1 C k-1?

[rotund delta]

The number of ways to divide 6 different people into two different teams, so that there are at least 2 people on each team. (The teams are not required to be the same size.)

Anyone mind explaining this to me?

[tacit estuary]

You could do the power set minus all the sets with 1 thing in it

And also minus the empty set

$2^6 -6 -1$

[vital dew]

RipeOrange

[tacit estuary]

Since a power set has $2^n$ element in it and 6 of them are just 1 person, and also subtract away the empty set

[vital dew]

RipeOrange

[tacit estuary]

Oh crap you can't have the sets of 5 or 6 either

2^6 - 6 - 1 - 6 - 1

Idek know anymore oof

[cerulean wind]

ah wait. so is it a different division of teams if 1 and 2 are on team A and everybody else is on team B vs if 1 and 2 are on team B and everybody else is on Team A?

or do we care who’s on what team

[rotund delta]

we care about not overrcounting

but, i think i solved it already

[cerulean wind]

um. that doesn’t answer my question, you will end up counting differently depending on this

[tacit estuary]

I think those would be counted as the same

Since it just says 2 different teams

[rotund delta]

yep

let me show you what i got

I’m sure divide, simply means to put 6 people

So it would be C(6,2) + C(6,3)

This particular case I shared was for 20 people

[cerulean wind]

that’s what i was getting

[rotund delta]

nice

[rotund delta]

a restaurant has n appetizers, m entrees, and k desserts listed on its menu.

what is the number of ways to order a single item, of any type, from the menu?

I think its C(n + m + k, 1)

[rotund delta]

then, the number of ways to order a full meal, such that a meal consists of one from each item?

i get C(n,1)C(m,1)C(k,1)

it is equivalent to nmk

[cerulean wind]

yes

[rotund delta]

ok, ways to order a sampler meal, which only consists of 3 different appetizer and a desert

i get C(n,3)C(k,1)

what if the order matters?

like, if the customer gets to specify the order in which the appetizers come

(n-1)(n-2)(n-3)! * C(k,1)

right?

man....im wrong

i dont know how to solve the last one

[cerulean wind]

i think that’s what this means

[rotund delta]

oooooo.....

i think the desert always comes last

[cerulean wind]

okay

then just n(n-1)(n-2)k

lemme just check again rq tho

[rotund delta]

yeah. i fixed the question, but....now im baffled lol

[cerulean wind]

so the order gets incorporated in the n(n-1)(n-2) part

[rotund delta]

yeah.

[cerulean wind]

no need to multiply by 3!

[rotund delta]

i get that. I was on talking about multiplying by a factorial...

so it would be as simple as (n)(n-1)(n-2)*k

[cerulean wind]

that was my fault. yea, that’s why i said i had to check again. something felt off

[rotund delta]

thanks....which accounts for the dessert coming in first or last either way

since it is the same exact number

[cerulean wind]

ye

[rotund delta]

thanks @cerulean wind

[mystic elbow]

Need help with 4.6,4.7

Ping me too please

[mystic elbow]

Anyone pls?

[tidal ibex]

can someoone explain me why this does not work and vice verca it works ? I have tried too prove it and i think it works

$P(A\cup B) \subseteq P(A) \cup P(B)$

[vital dew]

Michal

[pale epoch]

is P powerset?

[stray reef]

@tidal ibex ? ^

[tidal ibex]

yes

[stray reef]

consider: A = {1, 2, 3, 4}, B = {5, 6, 7, 8}

{4,5} is an element of P(A ∪ B) but is not a subset of A nor a subset of B.

[tidal ibex]

yes using counter example, but when i try to prove it, it works

[stray reef]

oh, you have a proof?

do share it with us then, so that we can point out where the faulty step is.

[tidal ibex]

ok, will send photo

[stray reef]

,rccw

[stray reef]

and since when does $X \subseteq A \cup B$ imply $X \subseteq A \lor X \subseteq B$?

[vital dew]

Ann

[stray reef]

@tidal ibex

[tidal ibex]

if X is subset of AuB then then x must be subset of A or B

[stray reef]

you're just repeating that statement all over again

do you really believe that it's true?

[tidal ibex]

no its not, but it looks it is

[stray reef]

i don't hear a clear "yes, i believe it's true" nor a clear "no, i don't believe it's true"

[tidal ibex]

its weird

[stray reef]

answer my question please

do you believe that if X ⊆ A ∪ B then either X ⊆ A or X ⊆ B?

YES or NO

[tidal ibex]

yes

[coarse cave]

well if A = {1, 2, 3} and B = {4, 5, 6}, and X = {3, 4, 5}, isn't it a subset of X ⊆ A ∪ B but not X ⊆ A or X ⊆ B? @tidal ibex

[stray reef]

okay, then please present a proof of this statement.

[tidal ibex]

I need to think more about it

[stray reef]

you've been presented with two counterexamples now.

take A = {1, 2, 3} and B = {4, 5, 6}, and X = {3, 4, 5}.

is X a subset of A?

is {3,4,5} a subset of {1,2,3}?

[tidal ibex]

Not

[mystic elbow]

Anyone? 4.6 and 4.7 only

[north girder]

Is the answer 17/7 hrs?

3/7 + 2 = 17/7 ??

[proven silo]

no

call the break time x and write an equation using the information given

[north girder]

3x/7 ?

[proven silo]

an equation has an equality sign does it not?

[north girder]

3x/7 = 2 ?

[proven silo]

no

(he spents his time....)=(time spent)

[north girder]

I am confused

[quaint star]

If you say 3x/7 = 2, you are saying the 3/7 of his time he spent of grocery shopping = the 2 hours he spent buying furniture

That's not what they say

[proven silo]

If I spend 1 hour shopping, 2 hours walking, 2 hours eating the equation is

1+2+2=x is it not?

for total time spent

apply the same logic

[north girder]

So, 1/7 + 2 = x ?

[proven silo]

where does 1/7 come from?

[north girder]

Sorry

3/7 + 2 = x ?

[proven silo]

he doesn't spend 3/7 hours on grocery shopping

so not 3/7 either

[north girder]

He spends 3x/7 grocery shopping

[proven silo]

there you go

[north girder]

Then what is the equation?

[proven silo]

fix the equation you wrote above

and that is the equation

[north girder]

3x/7 + 2 = ?

[proven silo]

where did x go?

[north girder]

3x/7 + 2 = x ?

[proven silo]

yes

[north girder]

3.5 hours = x

[north girder]

Is this the answer?

[proven silo]

,w 3x/7 + 2 = x

[vital dew]

Results provided by WolframAlpha

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

Requested by ScapeProf#9427

[mystic elbow]

Please

Help

Just 2 questions

[proven silo]

probably gonna get more help if you explain the context, what is T(n)? what are we asked to do?

its just a picture with 0 context

[tidal ibex]

Anybody know how to continue in this proof ?

[weak wadi]

General advice, when asking for help. Make it as easy as possible for people to help you. For example, post in formats that don't need conversion to read. I suggest you rotate your pic.

[stray reef]

you forgot some parentheses...

if you want to go this way, all three conjunctions have to be wrapped in parentheses

(x in A1 & x not in A2) or (x in A2 & x not in A1) or (x in A1 & x in A2)

then i suppose you could do a lot of Boolean algebra to expand this out into an AND of 8 ORs and then simplify some of those ORs away...

or you could just not bother with all that, and make a venn diagram.

[shadow shuttle]

I have one question: There are 45 males and 35 females in the row. Proof that there is existence of a couple of males which between them is 8 people.

Thanks in advance

[stray reef]

@shadow shuttle have you made any progress on this so far?

[shadow shuttle]

I have tried Dirichlet's principle but it seems not work

[shadow shuttle]

[stray reef]

okay, how exactly have you tried to use dirichlet's principle?

[shadow shuttle]

It's kind of a1, a2 ,a3, a4, a5, a6, ... , a1 +8, a2+8,.

then at least 2 numbers are equal

but it makes no sense...

[stray reef]

what are those numbers meant to represent?

sounds like you're unclear on that, and that's what's making you stuck

[shadow shuttle]

...

maybe

I'm trying to think about that but i'm not sure it works.

[stray reef]

"there exist two males with 8 people between them" can be rephrased as "there exists n ∈ {1, 2, ..., 80} such that the people at positions n and n+9 are both male"

where the positions are, of course, numbered from 1 to 80 in order

what i am going to suggest is this: try considering what happens if we FORBID any two males from having exactly 8 people in between

[shadow shuttle]

is it related to divisibility?

[stray reef]

...maybe it is, but i don't see how an answer to this question would help you.

[shadow shuttle]

maybe it doesn't have enough females to obtain that...

[stray reef]

consider the positions {1, 10, 19, 28, 37, 46, 55, 64, 73}
and then the positions {2, 11, 20, 29, 38, 47, 56, 65, 74}

and so on

for a total of nine sets of positions

[shadow shuttle]

...

could you give more hints @stray reef

[stray reef]

1, 10, 19, 28, 37, 46, 55, 64, 73

consider who can stand in these positions

in particular, consider that if there's a man on any position in this list, there has to be a woman on the next

[shadow shuttle]

oh

thank you so much, I figure it out

@stray reef So do you know when we should use Dirichlet's principle or counterpositive to prove something ?

or other methods ...

[stray reef]

you learn it from experience.

[weary tiger]

Hey guys/girls, Hope you're well! - Mature student here looking into a career change. Going to study A Level Maths,FM and Comp sci. Is Discrete math in Further math or is it in Maths also? I haven't actually looked into the syllabus on either, but it seems the more traditional route (A-Levels) is the preferred option for unis than a Access to HE Diploma as they lack the mathematics.

Thank you!

[shadow grove]

No idea about any of that, and I am certain the Danish school system is different from yours.

But discrete mathematics at my school/uni is basically combinatorics and then logic until first-order logics (Not necessarily in that order).

[covert marsh]

okay

explain to me if my logic is right

[cerulean wind]

“a map Y that contains n elements” what?

“if X is a subset of Y, then n must exist in both X and Y” probably not but again, what?

point is, could you give some context and try to be more precise with your thought process

[shadow shuttle]

@stray reef tks u so much, today I have passed my teacher's challenges.

[sand cipher]

is b,c,true and d false

is 5 and element of a or 5,7 or both?
and pretty sure 6 is a subset of a rite
and the last, would it be false since a is not an empty set?

[dense geyser]

b and c are both false

[sand cipher]

is it cuz b is 5,7?

i don't rlly understand c tho
is it cuz it's {6}?

[vital dew]

cgodfrey

cgodfrey

cgodfrey

[sand cipher]

i'm abit confused on the subset part,
from what i know is ex. C={1,3,{5}}
3 is a subset of C
5 isn't?

[dense geyser]

that's right

in that case, {5} would be a subset of C, not 5 itself

[sand cipher]

i see

[dense geyser]

wait

hold on

I got that wrong

3 is an element of C

but 3 is not a subset of C

because 3 is not a set

you could say that {3} is a subset of C, though

[sand cipher]

sorry i meant
if it was {3} is a subset of C

rite

[dense geyser]

similarly, {5} is an element of C, and {{5}} is a subset of C

[sand cipher]

ow so double {}

[dense geyser]

right, because the common element is itself the set {5}

so does that clear up b and c?

[sand cipher]

yep

then it seems like e is also false since it's asking {5,7}

but it is an element of A

[dense geyser]

right, so e and f show that distinction

[sand cipher]

alrite got it, thankyou @dense geyser

[dense geyser]

just to make sure, d is true

it's a fact that the empty set is a subset of every set

because it's vacuously true

[sand cipher]

ow i was wondering about that
i thought
case1: true since it exist in all set
case2: false since empty set must not have any elements in it

[dense geyser]

so the definition is that $A\subset B$ if, for every $x\in A$, $x\in B$

[vital dew]

cgodfrey

[dense geyser]

In this case, there's no element in A, so that requirement is vacuously satisfied

another way to think of it is that there are no elements in the empty set that aren't in A

so there's nothing to 'break' the definition

gotta go, but hope that clears it up

[sand cipher]

ye it did

thanks alot xD

[mystic elbow]

hi

is my answers correct

5.8 is little omega
5.3 big omega
5.4 is little omega

5.7 is big oh

??

[muted harness]

#elementary-number-theory

[hasty glade]

Should the question go there?

[muted harness]

Yeah.

[hasty glade]

Sorry, I thought that It was more related with discrete math, I will post it there then. Thanks for noticing that

[muted harness]

Np

[neat wyvern]

I need some fucking advice on discrete math, i am taking a cs course about functional programing and discrete mathematics and I am loosing my shit, we are getting weird fucking questions that no matter how much i try using the formulas we learn at class, i can never figure out. for example:

I need some plan or a resource to understand the whole concept, if anyone went through such a course please share with me any kind of good reliable source to study from.

ANY kind of advice will be truly appreciated

[muted harness]

Seems like you are dealing with combinatorics.

Why not try youtube videos?

[arctic tundra]

how can i prove |R x R| = |R| after proving |(0,1) x (0,1)| = |(0,1)| ? i have no idea what to do to continue the proof any tips?

[pale epoch]

biject R to (0, 1)

[arctic tundra]

thank you

[hybrid ether]

I'm not getting universal quantifiers in this context

[stray reef]

$S = {2,3}$, so $\forall x \in S$ is to be read as $\forall x \in {2, 3}$

[vital dew]

Ann

[hybrid ether]

There exists y belongs to T, for all x belongs to S, P(x,y)

[keen fractal]

hey guys im new to this can anyone help me simplify this

im tired of searching and my brain is broken

[fierce jungle]

Hey can someone give me a tip on how to solve this

A = B if A (symmetric difference) B = 0 with / inside of it

I need to prove it

[cerulean wind]

show that if A\B is empty then A is a subset of B.

note that the symmetric difference of two sets is (A\B) U (B\A). if this union is empty, then both of the above sets are empty.

[zinc karma]

Can anyone help with this question please?

[hidden crystal]

<@&286206848099549185> can anyone help me with this

[tepid mountain]

not really sure if this belongs here or not but are any of these correct, idk how to do this

i think i have to prove that they true

<@&286206848099549185> thanks

i posted in #help-25

[dusk lark]

bruh one of my friends needs help in set theory

i dont understand anything in this

can someone help

[cerulean wind]

what is n(p(A))?

[dusk lark]

idk

bro

literally

my friend needs it

so ya

[cerulean wind]

lol ask them

[dusk lark]

wh

o

[stray reef]

if your friend needs help, then why don't they come in here and ask it themselves instead of using you as a middleman?

[dusk lark]

bruh

cause he scared

i can give his discord if u want

i dont care if u help me or not

[stray reef]

here's the thing: if you, the middleman, claim not to understand anything, then we cannot do anything to help your friend through you

[cerulean wind]

scared of what

[dusk lark]

nvm

his account got disabled

[split drum]

Hi, could someone explain to me why 9.13 is transitive? I can't make sense of how the definition is being applied as there is only one relation in R.

[stray reef]

the definition of transitivity is $$(\forall x, y, z \in S)[(x,y) \in S \land (y,z) \in S \to (x,z) \in S]$$

[vital dew]

Ann

[stray reef]

when S = {(a,b)}, the premise is always false, so the statement is true vacuously

[split drum]

Ah, I see. Thank you 👍

[hybrid ether]

Hi

Anyone here?

A doubt

Why the quantified statement is true in 2.38

[stray reef]

@hybrid ether do you think it should be false?

[torn tendon]

the order of quantifiers is important here
when you say for all x exists y it means for any x you pick you can find a y such that x+y is prime
while when you say exists y for all x means a much stronger statement , for some y all the x you pick will imply x+y is prime

https://math.stackexchange.com/questions/491783/intuitive-reason-that-quantifier-order-matters this also might be helpful

[fierce jungle]

Oh thanks

[reef thistle]

Can infinite graphs have an irrational fractional graph colouring? Which numbers are possible as fractional chromatic numbers?

[tender kestrel]

can someone help me?

theres more to this review and i need help

[main cargo]

Hey guys, I made this exercise in combinatorics but I'm not sure if my reasoning is correct, if someone could help that would be very nice

[main cargo]

The first one is onto and one to one, second is neither, third is both, fourth is both

But you should learn how to do it yourself

[lost adder]

what's that textbook?

[split drum]

Mathematical Proofs: A Transition to Advanced Mathematics. (4th Edition) By Gary Chartrand, Albert D. Polimeni, and Ping Zhang.

[lost adder]

thank you

[split drum]

You're welcome

[reef thistle]

Just asking again:
Can infinite graphs have an irrational fractional graph colouring? Which numbers are possible as fractional chromatic numbers?

[forest latch]

hey, can someone give me a hint how to do this? idk how to create such kmap and what should i do then

[stray reef]

@forest latch what do the vertical pipe and down-arrow mean?

[tidal tulip]

can i get a problem check, my answer differs from the book: Let S = {− 2, −1, 0, 1, 2, 3}. Describe the following sets as {x ∈ S : p(x)}, where p(x) is some condition on x. the set is D={-2,2,3}. my answer is: D={x in S : |x| > 1} - is that correct as well

[pale epoch]

yes

[bitter moss]

Suppose you start with a cake of n times k square pieces. In each step, select a piece of cake that has two or more squares and break it into two parts along an arbitrary line, vertically or horizontally. Show that the cake is reduced to simple squares after (nk-1) breaks.

any idea how i can start?

[broken burrow]

Suppose a ∈ Z. If a^2 is not divisible by 4, then a is odd.
Solution:
Proof. (contrapositive) Suppose that a is an even integer. Then a - 2k for some
integer k. Therefore, a^2 - (2k)^2 - 4k^2, so since k^2 is an integer, a^2 is divisible by 4.

I didn't get the solution, could somebody explain it to me?

[bitter moss]

what didnt you get

also youve confused a few equal signs with minus signs

[broken burrow]

@bitter moss I didn't get where they got a^2 - (2k)^2 - 4k^2 from

[broken burrow]

No no, I found the answer on a website, that's how it was written

Here, question 4

[bitter moss]

yeah thats an equal sign dude

a^2 we know can be written as (2k)^2 which cn be written as 4k^2 which is divisible by 4

cause he said a=2k for some integer k

he just messed it up

[broken burrow]

@bitter moss
My answer was:
a = 2k
a^2 / 4 = i
(2k)^2 / 4 = i
4k^2 / 4 = i
4k^2 = 4i
k^2 = i

It doesn't seem to be 100% correct, does it?!

[bitter moss]

what is i

[broken burrow]

@bitter moss
An integer. I don't know if I can make that kind of assumption.

[bitter moss]

so you assume a^2/4 is an integer ok

i dont get how this proves a is odd though

oh because it is divisible by 4

fair enough

[broken burrow]

Yeah, you're right, my answer got very confusing. But now I understand it, thanks. Do you happen to know of a good book about discrete math?

[bitter moss]

lol no idea

[broken burrow]

lmao

But thx anyway dude, helped a lot!

[bitter moss]

np

your proof isnt perfect, but its almost correct

you at least proved its divisible by 4

[broken burrow]

@bitter moss
Yeah, I think I shouldn't have made that assumption a^2 / 4 = i

[bitter moss]

yeah

[bitter moss]

you basically did what this guy did anyway

just where did the a^2/4 part come from

just say a=2k
assume a^2=4
substitution
divide by 4

smth like that

[broken burrow]

I'm trying to say that a^2 divided by 4 equals to an integer

[broken burrow]

Alright!

[bitter moss]

yeah but it wouldnt be an integer if a isnt divisible

nvm its a good proof you got im just trippin

[broken burrow]

Makes sense

[broken burrow]

thx, I'm kinda new to this, I should study more

[bitter moss]

Suppose you start with a cake of n times k square pieces. In each step, select a piece of cake that has two or more squares and break it into two parts along an arbitrary line, vertically or horizontally. Show that the cake is reduced to simple squares after (nk-1) breaks.

can someone help me with starting this

[bitter moss]

oh wait is it cause when we divide (nk)! by (nk-1)! we get nk left and thats all the square pieces of the cake or smth?

[elder berry]

The easiest way that comes to mind is using induction two times.
First for n x 1 squares, then for n x k squares.

[bitter moss]

woah

[elder berry]

Do you mind explaining how factorials relate here?

[bitter moss]

well cause you can cut the cake that many amount of times

but theres no order to where you cut it

it was just a guess

[bitter moss]

im very interested in this though, why would this work?

and why for nx1 squares and nxk squares

oh to prove its for all of them

but yeah why would it work

[elder berry]

Well you first start with a row of the cake,
the idea is that for a singular row, it is incredibly easy to show that for n x 1 you need n-1 cuts

This is the first induction^

[bitter moss]

ok yeah

[elder berry]

Then, for the n x k case, you suppose you have to use nk - 1 cuts, (the base case is true via above induction), and the problem becomes much easier since you would need to cut the top row of this new n x (k+1) cake

[bitter moss]

mhm ok

i can wrap my head around that

but how do i prove that nx(k+1) is true if we divide by nxk cuts

[elder berry]

You need 1 split to separate the n x (k+1) cake into n x k and n x 1 cake
By induction, you need nk - 1 to split the n x k cake into unit squares
For the n x 1 cake, we already showed that is n-1 splits.

Summing up you have 1 + nk - 1 + n - 1 = nk + n - 1 = n(k+1) - 1 which is exactly what we want for that new case

||Since for n x (k+1) we need n(k+1) - 1 slices||

[bitter moss]

yeahh thats genius

lmfao

my professors gonna love this

he was expecting me to use some combinatorics or smth nope im using induction

thank you! @elder berry

[elder berry]

You should try a combinatorial approach as well. Induction is nice but isn't that satisfying

For some reason my mind is blanking so I'll approach this question later, see what you can do on your own

[bitter moss]

ight

ill try

[tidal tulip]

Thanks!

[elder berry]

Sorry to ping you again, but if you need a hint about the combinatorics approach, consider what happens when we cut the cake. For example, if I cut 1 cake with one slice, I get 2 different pieces.
Therefore, how many cuts would we need to get n*k different pieces

You can prove the result

[bitter moss]

Ohhhh

Yeah

That makes sense

Ty 😇😇😇

[real blaze]

Hey guys! First year in maths here. Was actually doing physics for the past weeks, but switched to maths.
There are some practice questions for this subject, but can’t quite get this one:

Prove that a set of n elements has 2^(n-1) - 1 partitions consisting of two classes.
Since this is about partitions and not subsets, I don’t have the same intuition for it yet for concepts like induction and such

Any tips would be appreciated

[coral raven]

every element can be on one side of any given partition or another

so 2^n

however it doesn't matter which side you call 'left' and which side you call 'right'

so 2^(n-1)

also you can't have all of them on one side

so 2^(n-1) - 1

[real blaze]

Wow! That’s pretty intuitive

Thanks a lot

[weary tiger]

Heyo, not sure I quite understand the working for this. To prove a union of two countable sets is countable, do I make a bijection between them?

[quaint star]

No, a bijection from N to the union

[weary tiger]

So that would just be x/2 for even, log3(x) if odd?

[quaint star]

Are you mapping N to A union B?

[weary tiger]

A union B to N

[quaint star]

It's not a bijection

2 maps to 1, 3 maps to 1

[weary tiger]

Oh crap I see, you're right

[quaint star]

Easier to go from N to A union B

Let the odd numbers map to elements od A, and the even numbers map to elements of B, or something like that

[weary tiger]

Cheers

[weary tiger]

Don't think this works

Nothing maps to primes

[quaint star]

The only prime in A union B are 2 and 3

And if you did it the way I envisioned, 1 would map to 2, and 2 would map to 3

[weary tiger]

Doesn't every element in N have to be reachable though?

Or am I not understanding countability

[quaint star]

I am mapping from N to A union B

So every element of A union B must be mapped to

f: N -> A cup B

[weary tiger]

Oh 🤦

You're right, my bad

[quaint star]

👍

[north dust]

This binomial theorem is confusing me, ahh

[wraith obsidian]

Happy diwali!

It's diwali Mike!

[queen raptor]

Can any1 explain how v got the underlined step

[stray reef]

$n = 6q+3 \equiv q+3 \pmod{5}$ by the steps immediately preceding your underline

[vital dew]

Ann

[queen raptor]

Yes I got that step but how is n=q+3

[stray reef]

???

n = 6q+3 !

at no point was anyone claiming n was equal to q + 3

n is congruent to q+3 mod 5

[queen raptor]

Gimme a min

[queen raptor]

Okay I got till here

But the next step ie q+3 congruent to 2(mod5) I did not get

[stray reef]

you are given that $n \equiv 2 \pmod{5}$

[vital dew]

Ann

[queen raptor]

Yes

Im sorry im new to this topic

But how will that give the underlines step

[stray reef]

n, 2, and q+3 are all congruent to each other mod 5.

[queen raptor]

Okay so if 2 equation r congruent to each other then v can rearrange right

[stray reef]

......

i think you're both overthinking it, and confusing the words 'expression' and 'equation'

you have that $n \equiv 2 \pmod{5}$ and $n \equiv q+3 \pmod{5}$.

[vital dew]

Ann

[stray reef]

do you understand this or not?

[queen raptor]

Yes

I understand

[stray reef]

do you understand how those two statements imply $q+3 \equiv 2 \pmod{5}$?

[vital dew]

Ann

[queen raptor]

Is it because the dividend and the module are same in both expression

Is that y it's congruent

sorry i dint do my hw😅

Thnx anyways

[tidal tulip]

can i do a proof check on this? it seems so obvious, i want to make sure i am giving the correct details: prove if A is a subset of B, and B is a subset of C then A is a subset of C. proof: we have by assumption that for all x in A, x in B. we know by assumption every element in B is in C, and these include all of the elements of A in B. therefore since every element of A is in C, we see A is also a subset of C..

[pale epoch]

sure, works

[sour dove]

can someone help me with a problem?

Take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Then,using Hall’s marriage theorem, show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (Ace, 2, 3, ..., Queen, King).

[tranquil jungle]

when I do negation of "at least 2 students have the same birthday", do I apply the negative to both "at least" and "same"? so no more than 2 student have different birthdays or something

[proven silo]

If you just think logically that statement is false if no students have the same birthday

[tidal tulip]

Find two sets A and B such that A is both an element of and a subset of B: would this work? A = {{1}} and B = { {{1}}, {1} }, because every element in A, namely just {1}, is an element of B (satisfying A is a subset of B) and the set A, namely, {{1}} is an element of B

[tranquil jungle]

ohhhh, I treated the at least 2 part too literally

[tidal tulip]

anyone?

[storm pond]

Is there alternative way to list down all the proper subset without approaching the answer like the example? Tq. Example, list down all the proper subset of set X: {1,2,3,4.....,56,57,58,59,60} -- Ans: Proper Subset of Set X: {{Ø},{1},{2},...,{60},{1,2}, {1,3},...,{59,60},{1,2,3},...,{58,59,60},.......}

[stray reef]

...do you REALLY want to list all 1,152,921,504,606,846,976 subsets by hand?

or rather, 1,152,921,504,606,846,975 if you only want proper subsets

[tidal tulip]

Is my solution correc: Find two sets A and B such that A is both an element of and a subset of B: would this work? ---- A = {{1}} and B = { {{1}}, {1} }, because every element in A, namely just {1}, is an element of B (satisfying A is a subset of B) and the set A, namely, {{1}} is an element of B

[storm pond]

Yes, but not as many as the example I given just now, the question i am doing right now required me to list alll (2^19)-1 = 524287 proper subsets. Thats why I am finding alternative way to answer it 😅

[coral raven]

yes

you can do it more simply, though

[tidal tulip]

ok

[coral raven]

let A be 0

let B be {0, {0}}

wait

ok so by 0 here i mean the empty set, to be clear

[tidal tulip]

ah

[coral raven]

waaait

no, i'm a fool

let B be {0, {0}}

wahsjklfsdhjlkfsdh;klsfd

i'm too tired for this

[tidal tulip]

A= {0} (where 0 means empty set), then {0} is an element of B, and every element in A (namely just 0), is in B

so that does indeed work

[cerulean wind]

bruh, just A = 0, B = {A}

empty set is a subset of every set

A is an element of B

[weary tiger]

pretty basic question, but how do we arrive at the formula for d ?

[tidal mica]

Hey guys, does anyone study discrete mathematics, preferably using Martin Aigner's book? I'd love to have a partner to study and exchange information with (I can even read to you)

[pale epoch]

if you have the prime factorization you can build all the divisors from that

every divisor has a as a factor 0, 1, ...,p times, b as a factor 0, 1, ..., q times

and so on

so you just choose the exponent from the set {0, 1, ..., p} for a and so on

[real blaze]

I don’t see how 0 makes sense though

[pale epoch]

surely 1 is a divisor of N

1 = a^0 * b^0 * ...

[real blaze]

Since every of those primes^0 will equal 1 nonetheless, should not count it more than once

[pale epoch]

and surely b, b^2, ... are divisors

for those you need p=r=...=0

[weary tiger]

ohh okay I didn't realise at first the product rule can be used when you have 3 choices at one point as well

[pale epoch]

also prime factorization is unique so each choice will correspond to a different number

[weary tiger]

yeah ofcourse, I got the concept of the factors, I was just stuck in how to think about calculating it, because I was like trying to view it as a combination problem and stuff

[tidal tulip]

is there anything incorrect that i stated, is that why you said this?

[cerulean wind]

no. this is just minimal

which is what some others were trying to do

[tidal tulip]

k

[wheat leaf]

How would u go about doing part a

[narrow sorrel]

How do I approach this question? Do I need to assume n is even or odd?

[coral raven]

consider the factors and then think about even/oddness

[narrow sorrel]

@coral raven can I factor it out like (n-1)(n+5) and say 1<(n-1)<(n-1)(n+5) and 1<(n+5)<(n-1)(n+5) so it is composite?

[coral raven]

wait no yeah

it's not even about even/oddness

yeah that's it

[narrow sorrel]

@coral raven How do I prove that both n-1 and n+5 are smaller than the original polynomial?

[coral raven]

if n+5 = (n-1)(n+5), n-1 = 1, more or less

and similarly for n-1

[narrow sorrel]

@coral raven Thank you so much!

[coral raven]

np

[split drum]

Hey, could someone help me figure out a formula for this recursive function? It's $a_n = 3a_{n-1} - 2$. I tried $a_n = 3^n + 1$ but that only works up to $n = 3$

[vital dew]

Umiguess4000

[split drum]

<@&286206848099549185>

Nevermind, I did the arithmetic for $n = 4$ wrong...this formula works.

[vital dew]

Umiguess4000

[tender kestrel]

i need help

[spice dock]

To start out for number 9:
x <= x since x = x, so R is reflexive.
2 < 3 but 3 !< 2, so R is not symmetric.
if x < y and y < z, x < y < z, so R is transitive.

For 10: Since 1 is a real number, we can evaluate the relation on 1. However, 1^2 + 1^2 = 2 != 1, and as such !1C1, meaning that this relation is not reflexive.
Since x^2 + y^2 = y^2 + x^2, this trivially means C is symmetric.
Simply observe 1C0 and 0C1 to see that this is not transitive.

For 11. If x >= 0, x * x >= 0 since its the product of two positive numbers. If x < 0, since x * x is the product of two negative numbers, x * x is positive, meaning that xDx and as such D is reflexive.
Since xy = yx, we know this obeys symmetry.
Suppose xDy and yDz. We know that if one is positive than the other is positive (and also if one is negative than the other is negative) for each x, y, and z, meaning that xDz is positive and as such D is transitive.

[elder steppe]

I'm rly not sure how to use the fact that my teacher gave at the end of the question

I have the base case down but I don't know how to approach the inductive step while making sure i use that property

[cerulean wind]

what work have you got so far? if you just try writing some things down, it should naturally pop out

[weary tiger]

what exactly is an equivalence class?

I see it all the time in different kinds of maths like "equivalence class of functions" and stuff like that

I know what an equivalence relation is but what's an equivalence class?

[elder steppe]

nvm i did just that and figured it out

[stray reef]

@weary tiger formally, given an equivalence relation R, the equivalence class of a point a, denoted [a], is the set of all elements that are equivalent to a under R

[weary tiger]

ahh

[stray reef]

you can imagine an equivalence relation as splitting the set it's on into buckets such that two elements are equivalent if and only if they go in the same bucket

those buckets are the equivalence classes

[weary tiger]

so 'a' can be any mathematical object?

[stray reef]

yes, of course.

[split drum]

Could someone help me as to how to prove that the following is an equivalence relation: Let $R$ be a relation on $\mathbb Z \times \mathBB Z$ such that $(a, b)$ R $(c, d)$ if and only if $a-c = 2(b-d)$. I know that I have to show that it is reflexive, symmetric, and transitive, but I am stuck as to how.

[vital dew]

Umiguess4000
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[split drum]

For reflexive, I guess I would need to show that (a, b) R (a, b)?

omg, wait I think I just realized how to do it

In the equation a gets paired with a and b gets paired with b, so you end up with $a - a = 2(b-b)$ so $0 = 2(0)$ and thus (a, b) R (a, b)

[vital dew]

Umiguess4000

[split drum]

Coffee must have kicked in or somthin'

For symmetric, I know I need to show that (a, b) R (c, d) $\rightarrow$ (c, d) R (a, b). Would this mean show that $b-d = 2(a - c)$ or that $c - a = 2(d - b)$?

<@&286206848099549185>

[vital dew]

Umiguess4000

[stray reef]

c-a = 2(d-b)

[split drum]

Ah ok, so could I just multiply both sides by -1?

[stray reef]

perhaps

[split drum]

Are you implying there is a better way to show it?

[stray reef]

yeah, you can do it in one fell swoop

define a function $f: \bZ^2 \to \bZ$ by $f(x,y) = x - 2y$; you can show that $(a,b) R (c,d)$ iff $f(a,b) = f(c,d)$

[vital dew]

Ann

[stray reef]

which makes it almost obvious that R is an equivalence relation

[split drum]

Wow, that's way more elegant than anything I would have thought of.

[stray reef]

yeah in fact all equivalence relations have an associated function like this

[split drum]

My professor didn't mention anything relating to this. Do you know where I would learn more about this?

[gray minnow]

Question: what are the primary uses of the Matrix Tree Theorem? It seems important and should be useful in lots of cases, but I can't really find anything on uses in other theorems or for practical matters

[tired moat]

I was solving this problem: How many distinct strings of 0s and 1s of length n are there, if they must have either 00000 or 11111 as a substring.

I managed to solve it with dynamic programming but Im wondering if there is also an explicit solution for it. Does anyone see it?

I was thinking if I denote a_i, as string of length i satisfying the condition, I could get some recurrence formula for it and then solve that

Thought I could put: a_i = (number of strings with last 5 characters being the same) + (# of strings with last 5 characters not all the same)

And I know the first term is something like 2^(i-4), but I'm not sure how to do the second term. Is this even the right approach?

[pale epoch]

well

if it needs to include 00000 as a substring, you have n-5 digits left that could be whatever

so 2^(n-5) choices for those

and then there is a choice as to how many to put before the 00000

those are n-4 choices

i think this should give you all the strings only once?

then do the same for 11111

and then figure out how many include both of those

[tired moat]

Won't we double count though? Like for example 1111100000

[pale epoch]

is it?

[tired moat]

Where does this come from?

[pale epoch]

so in my head

i first generate a randoms tring of length n-5

and then decide to put the first 0, 1, ... characters before the 00000

and then the rest after

i think this should give me every string in precisely one way

like 1111100000 is the result of generating 11111 and putting everything in front

[tired moat]

Hmm Im not sure. Like what if a string was just 10 0s

Then you would count it as 5 in front and 5 in back

[pale epoch]

ok true

[tired moat]

And 1111100000 you would count once when considering all possibilities for starting with 00000 and then puttings 1s in front. And then again when doing the same for starting with 111111 and putting 5 0s at end

I was trying it this way too and those "special cases" kept messing me up

(not sure if there even if a nice solution btw. Just thought there could be)

[pale epoch]

yeah, so the general idea is to first count all that have 00000, then all that have 11111 and then all that have both

there probably is a nice formula

but yeah, mine doesnt quite work

[tired moat]

Yeah something like that probably but not sure exactly

[pale epoch]

ok, i thought a bit more
this is harder than i thought

you can try setting up some kind of recurrence relation for strings of length n that do not include either of those patterns

or some inclusion exclusion stuff possibly

[pale epoch]

ok i think you can reduce this to linear algebra:
let a_{n, k} be the number of strings of length n including neither 00000 nor 11111 as a substring that end in k 0s (k = 1, 2, 3,4)
let b_{n, k} be the number of strings of length n including neither 00000 nor 11111 as substring that end in k 1s (k= 1, 2, 3, 4)
let a_n be the number of strings of length including neither 00000 nor 11111 as substring that end in at least one 0 and b_n similar. let c_n = a_n + b_n

you can essentially reduce this down to some bigass recurrence relations and turn it into a problem of linear algebra, its not pretty but should work

exercise for the reader: actually calculate it and generalize it

[graceful nimbus]

Is the topic "mathematical induction" covered in this section?

[pale epoch]

yes or #proofs-and-logic

[graceful nimbus]

so normally, after substituting n = k in the given equation, we then take n = k+1 and then add it on both sides to the n = k equation right? so why is that not the case here

or did i get something wrong

[pale epoch]

how do you think it should look instead?

[graceful nimbus]

k + k + 1 < 2^(k) + k+ 1

[pale epoch]

ok, so adding anything to both sides is the wrong way to think about induction

you might have seen some problems where this is happening (or it seems like that anyway) but its no general approach

in this case all you have to do is show that $k + 1 < 2^{k+1}$ while using the fact that $k < 2^k$ (this is the induction hypothesis)

[vital dew]

Lochverstärker

[graceful nimbus]

so i have to figure out this every time I see something like this i cant just add n = k + 1

[pale epoch]

indeed

in general you have some statement $P(k)$ that depends somehow on an integer $k$
in this case the statement is $k < 2^k$

[vital dew]

Lochverstärker

[pale epoch]

in the last step you then have to prove that $P(k+1)$ is true while using the fact that $P(k)$ is true

[vital dew]

Lochverstärker

[graceful nimbus]

alright!

tysm for the explanation

[pale epoch]

when you proved that the sum of the first n number 1+2+...+n = n(n+1)/2 then it looked like adding n+1 on one side

but thats not really what was happening

(i assume this is where you saw this)

[graceful nimbus]

yea

oh shit sry for the ping

[pale epoch]

all good

[tired moat]

Ty loch. Your recurrence relations look promising

Not gonna bother actually trying to compute it.. Was just wondering how it wouldve been done 😄

[tired moat]

The 2nd part is easy right? First one looks kinda like arithmetic series

(besides the limits)

[vital dew]

c squared

[cerulean wind]

i leave the rest to u

[wheat leaf]

Can someone verify if this negation is correct

[fresh venture]

Plz help me with this

[tiny dragon]

What is P(x)? I'm a beginner

the set of all elements x in S such that P(x) is true.

What does P(x) mean?

[weary tiger]

elements satisfying P

[pale epoch]

P is some proposition that depends on x

like "x is even"

[tiny dragon]

How do you read it?

[pale epoch]

"P of x"

it's essentially a function from a set of elements into {true, false}

[tiny dragon]

Understood, thanks.

[fresh venture]

Anyone?

[tidal tulip]

Let (a, b) be an open interval of real numbers and let c ∈ (a, b). Describe an open interval I centered at c
such that I ⊆ (a, b) --- my question is what does "an open interval I centered at c" mean

[haughty garden]

my guess would be something of the form (c - eps, c + eps)

So you take some subinterval of (a, b) that contains c and the end points are equidistant from the point c

[rugged sorrel]

It feels like such a vague question.

[tidal tulip]

what is eps? yeah, this is from an intro to proofs book and there is nothing in the chapter about intervals being centered so maybe i should skip the question

[haughty garden]

I just shorthand wrote epsilon but in this context, epsilon is just a placeholder for some small positive value

[tidal tulip]

i dont really get it, so if you have the interval (1,5) and pick c=4 then I=(3,4), but what does this centering mean here

per this solution

assuming they mean min(|a-c|, |b-c|)

i dont understand what center means lol

[haughty garden]

Well, if c is contained in (a, b), then a < c < b can be assumed

[tidal tulip]

thats the only thing the text says about inetrvals

so i dont udnerstand this problem

can you explain what the problem is asking and why the solution i posted above is the solution

the book isnt being self-contained here

[rugged sorrel]

It was already mentioned, but "centering at c" means c has the same distance from the two end points in the new interval.

[tidal tulip]

so if (a,b) = (1,5) and I let c=4, then 4 has the same distance from the end points in the interval (3,4)?

that doesnt seem to work

[rugged sorrel]

How does 4 have the same distance from 3 and from 4?

[tidal tulip]

thats what im asking

r=min(c-a, b-c) = min(4-1, 5-4) = min(3,1) = 1 . I = (4-1, 4+1) = (3,5)

so c=4 has the same distance between 3 and 5?

[haughty garden]

Another way to think about "centering at c" is to think of c as the midpoint between your two end points

[tidal tulip]

i see

so the distance between 3 and 4 is 1

the distance between 4 and 5 is 1

[haughty garden]

Yup!

[tidal tulip]

so (3,5) is centered at 4

[haughty garden]

exactly!

[tidal tulip]

ok! i see ty

it just means to find a sub-interval I that is centered at c, such that c is equal distance between the end points in I

[haughty garden]

Centered at c already imply "equal distance between the end points" but yes

[tidal tulip]

ok ty for helping me understand it

[haughty garden]

no worries 🙂

[polar vault]

does anyone know the symbol for the set of all cardinal numbers (including natural numbers, aleph numbers, beth numbers etc)

[quaint star]

I believe there is no such set

[stray reef]

yeah, it'd be a proper class.

[broken mauve]

How can I show that this holds: $\binom{n}{k} \leq \frac{n^k}{k!}$ for $n, k \in \mathbb{N}$

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[stray reef]

isn't $\binom{n}{k}$ equal to $\frac{n(n-1)(n-2)\dots(n-k+1)}{k!}$?

[vital dew]

Ann

[broken mauve]

yeah

My ideas so far are: $\frac{n!}{k!(n-k)!} \leq \frac{n^k}{k!} \iff \frac{n!}{(n-k)!} \leq n^k$

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[stray reef]

so what's the issue??

there are k factors in the numerator, each one less than or equal to n.

thus you have n(n-1)...(n-k+1) ≤ n * n * ... * n = n^k

that's it

[broken mauve]

yeah, but wouldn't i have to show this by induction

[stray reef]

are you explicitly instructed to use induction?

[broken mauve]

not rlly, but i'm explicitly instructed to be precise with proofs

[stray reef]

so, you're not explicitly instructed to use induction.

which means you don't have to show it by induction.

[broken mauve]

the thing is

idk whether they will count that as a "proof"

proving $\prod_{j=1}^{k} n-j+1\leq \prod_{j=1}^{k} n$ was my idea

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[weary tiger]

But this is pretty much obvious right

[broken mauve]

it is obvious and trivial, but im in the early stages of uni, so it won't be that "obvious"

and we've just introduced ordering axioms

so i'm sure i'll need to be super precise

[weary tiger]

I mean, its enough to say that every term in the product on the left is smaller than n

by smaller I mean leq obviously

[broken mauve]

yeah

I mean I also had to prove that $(-1)^{2n} = 1$

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[broken mauve]

if i were to prove it by induction, how would i go on

[broken mauve]

this.

[torn tendon]

check base case-->assume true to n-->check for n+1

[broken mauve]

checking base

so n = 0

what would be put for k?

[torn tendon]

k

you're inducting on n

[broken mauve]

ok, so we get $\prod_{j=1}^{k} j-1$ and $\prod_{j=1}^{k} 0$

[weary tiger]

I guess you should start the base case with n=1

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[broken mauve]

why?

[weary tiger]

actually doesn't matter

Well, actually... you then have stuff like 0^0 assuming 0 in N

[broken mauve]

oh, we assumed that 0^0 = 1

[weary tiger]

okay then n=0 obviously true

[broken mauve]

so we do put something for k?

[weary tiger]

k is natural

you can assume k \in {0,...,n}

[broken mauve]

okay, yeah

so k can only be 0

thus n = 0 is correct

so now we assume that $\prod_{j=1}^{k} n-j+1\leq \prod_{j=1}^{k} n$ and deduce \ $\prod_{j=1}^{k} n-j+2\leq \prod_{j=1}^{k} n+1$

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[broken mauve]

with $0 \leq k \leq n+1$, right?

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[broken mauve]

what do i do next

[weary tiger]

yeah idk how to prove it using induction

only idea that comes to mind is like looking at binomial theorem

[broken mauve]

what do you mean by this

[weary tiger]

sorry I meant binomial theorem I guess

[broken mauve]

I mean

so we you want to use the identity for the $\binom{n+1}{k}$

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[broken mauve]

showing that $\binom{n+1}{k} \leq \frac{(n+1)^k}{k!}$

[vital dew]

˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞˞

[weary tiger]

No, perhaps looking at $(n+1)^k$ as $\sum_{j=0}^{k} \binom{k}{j} n^j$

[vital dew]

catfan1337

[broken mauve]

okay, yeah, and then?

[weary tiger]

but honestly its probably a mess

as I said at the very beginning, you prove it in one line saying every term on the left is smaller than n

and its gg

[broken mauve]

hmm

[cerulean wind]

offering an alternative approach:
show that the number of strings of length k from an alphabet of length n is k! • (nCk). then get an injection from that set into the set of all k-tuples

[broken mauve]

that sounds really hard to me

[cerulean wind]

the injection is trivial

counting the number of strings also isn’t too bad. this can be viewed as counting the number of injections from a k element set to an n element set if you have to be technical.
otherwise, you can just say, i have n choices for the first slot, n-1 choices for the second slot… n-k-1 choices for the kth slot. done

but idk. if you’re going to do induction and over complicate it anyway, why not just prove these related results while ur at it

[broken mauve]

maybe

ill try

[polar vault]

is there a symbol for the proper class of cardinal numbers?

[minor lake]

okay so

there's this consensus between math and programming

programmers are programmers- and they happen to have "precedences" regarding opreators, and, or as well as not

and it goes as following: not, and, or

now when I learnt about those in my course, I never considered that they had an order- they just seemed to be concisely written in a such way that the reader can understand wtf is meant in a problem or something

so

do they have an orders or not?

on the wikipedia page I can't find anything regarding some sort of priority or ordering, I'm just gonna assume so far that I'm blind

[pale epoch]

this is usual convention

when in doubt add parentheses

[minor lake]

is it doe?

if possible I'd really appreciate if you could quote something

I'm not sure if there's something on wikipedia (there seems to be nothing...)

as for author books I fear that they could be opinionated

[pale epoch]

https://en.wikipedia.org/wiki/Logical_connective#Order_of_precedence

[kind hollow]

how is this pronounced and what does this mean?

[pale epoch]

depends on context

probably "precedes or is equal to"

meaning depends even more on context

[kind hollow]

okay that makes sense on the examples im seeing thanks

[toxic ermine]

Hey friends, can you help me with some proof questions?

All I'm getting is that the first one is false, but it has to be true, so I'm pretty much stuck 😦

[proven silo]

wdym you get it to be false?

that implies you found a counterexample (which doesn't exists because it is true)

[toxic ermine]

I guess I shouldn't have ignored the brackets, I don't really know what they mean

[proven silo]

,w mathematical definition of floor

[vital dew]

Results provided by WolframAlpha

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

Requested by ScapeProf#9427

[toxic ermine]

So both [x+1/2] and [x+2/3] are integers?

[proven silo]

Yes the floor function rounds, as it said in the definition above

[toxic ermine]

thanks, I did the first one:), could you give hint on what I should do on the second one.

[proven silo]

n is an integer I assume?

Then just check the two cases, either n is even or n is odd

[toxic ferry]

is v in tau_v?

[rugged sorrel]

What is your definition of a path?

[toxic ferry]

An ordered set of vertices

I'm wondering if an initial point can also be a terminal point

[rugged sorrel]

If the definition is "an ordered set of vertices", then it can be. A "ordered" singleton is an ordered set.

Unless the definition of "initial" or "terminal" points explicitly forbids it.

[toxic ferry]

mmmmm

I'm leaving out a detail my bad

nvm then ty

[willow ocean]

can someone explain this algorithm to find a Eulerian circuit to me.

I've read it multiple times and has also searched the web for better explanations but couldn't find any...
if someone can explain it to me then it'd be of huge help
thank you

its related to computer science

[tidal tulip]

Could someone check my work to see if it is correct:

Give examples of three sets A, B and C such that
(a) A ⊆ B ⊂ C
(b) A ∈ B, B ∈ C and A /∈ (not an element of) C
(c) A ∈ B and A ⊂ C.

(a) A= N, B=Z, C=R

(b)
A = {1}
B= { {1}, 2}
C={ { {1}, 2} }

(c)
A={1}
B={ {1} }
C={1,2}

[weary solstice]

@tidal tulip Looks correct to me

[tidal tulip]

@weary solstice ty for checking

[weary solstice]

np

[weary tiger]

Why in the axioms for a projective plane assume 4 points s.t. no line incident with more than 2 of them instead of assume 3 points s.t. no line is incident with all of them?

3 points, set of lines {{A,B}, {B,C}, {C,A}} seems like a interesting example

[weary tiger]

<@&286206848099549185>

[hybrid ether]

Hi

Got a help

[weary tiger]

what

[toxic ferry]

when you show that two graphs are equal, is it identical to showing two sets are equal?

[coarse prawn]

This question says “prove or disprove the following statement”

d) this is solution. I’m wondering how did they put it in that form to solve? I don’t understand if this was even proven or disproven?

[elder berry]

They've proved it. It is a geometric progression, and the sum of a geometric progression is given by a well known formula. If you know it, you can apply it here

[coarse prawn]

Whats the name of the formula

[elder berry]

Formula for the sum of a geometric progression

[rocky apex]

Or you can prove by induction if you know that ;)

[coarse prawn]

Thank you so much, I’ve been trying to figure out how they did this. I am going to watch some YouTube videos but I really appreciate the help 😭

[sand cipher]

how would i do this?
first i would do x=4q where q is an integer
x=2k where k is and integer
fill in q with -1 => x=-4
fill in k with 2 => x=4

proves that both is true

so it show that A is subset of B and B is subset of A

[weary solstice]

@sand cipher You want to use the element method of proof here.

What you want to show is that any element you choose from A is also in B, but I believe what you have shown so far is that one element from A (specifically -4) is in B

[sand cipher]

wait so what i should've done is

fill in q with -1 => x=-4
then do B => x=-4, 2|x = 2|-4 = -2 which is an integer and proven

fill in k with 2 => x=4
then do A => x=4, 4|x = 4|4 = 1 which is an integer

[sand cipher]

and this prove for both element A and B

[weary solstice]

@sand cipher You want to keep things more general in order to prove a statement for all elements in A, I believe you don't want to actually fill in q or k with numbers. Start off by choosing a particular but arbitrarily chosen element of A, call it anything you want, say x, and then using just the fact that 4|x, can you show that 2|x as well? This will show that the particular but arbitrarily chosen element of A, is also in B, which proves A is a subset of B (all elements in A are also in B).