discrete-math

[pale epoch]

this is unhelpful

[silk grove]

You assume 2k-1

Then you do 2k+1

Same for even

[pale epoch]

or at least not needed at all

[silk grove]

Oh okie

[dense creek]

oh yeah @pale epoch I do have that

[pale epoch]

well, you can do it that way, try it maybe

[dense creek]

I do not know how to continue it

[pale epoch]

just apply the induction hypothesis

you know that $\frac{k+1}{2} < k$

[vital dew]

Lochverstärker:

[silk grove]

I’ll brb

[pale epoch]

so by induction hypothesis $f(\frac{k+1}{2}) = (\frac{k+1}{2})^2$

[vital dew]

Lochverstärker:

[dense creek]

I am assuming you are using strong induction?

[pale epoch]

yeah

[silk grove]

I really wanna help but I’m not at my computer

[dense creek]

It's ok @silk grove

[pale epoch]

i'm assuming strong induction

[dense creek]

why is f(k+1/2) = (k+1/2)^2?

[pale epoch]

by induction hypothesis

[dense creek]

ok

oh

[pale epoch]

as (k+1)/2 < k

[dense creek]

let me try

[pale epoch]

no

it's {(3,{1,2}), (3,{4,5}), (1,{1,2}), (1,{4,5})}

yw

i have no idea and i don't care really

[near prawn]

t!rep @cursive elk

rip bot

[dense creek]

I have one more question

Using regular induction, I understand that adding one more element in the set will multiply the size of the set to the previous set because there is one more location that the elements can move to, but I am having trouble showing it mathematically

[dense creek]

<@&286206848099549185>

[hardy viper]

@dense creek you can just try to explain all the new permutations in the n+1 case

like explicitly say some of the permutations are {n+1, [permutations of n]}

same with any other position of n+1

[dense creek]

Is that proof by induction though?

[hardy viper]

for the full proof you need the base case too

[dense creek]

I've only been exposed to mathematical induction

Haven't really tackled a question using words so I don't know if it counts

[hardy viper]

ohh gotcha

induction proofs look like this

[dense creek]

I understand but, is there anyway to show that adding a new element will multiply the existing permutations by the size of the new set?

[hardy viper]

yea with what I started with

start with the permutations of n objects, then add {n+1} before, after, or in between it, for n+1 total places you could put it

giving n!+n!+... (n+1 times) for (n+1)!

[dense creek]

Can you clarify on that?

What do you mean add {n+1} before, after or in between it?

[hardy viper]

uhh like for n=3

[dense creek]

I approached this using regular induction, so my only base case was n = 1

[hardy viper]

when going to 4, you have the permutations with 4 first {4,1,2,3} {4,1,3,2} etc

then the ones with 4 in the 2nd position {1,4,2,3} {1,4,3,2} etc

[dense creek]

So what you are saying is that the number stays still while all of the other numbers permute as usual just like in the set before?

new element added stays still*

[hardy viper]

yea, each case is a position for the new number (4)

[dense creek]

But why would that multiply the previous amount of permutations by the size of the new set?

[hardy viper]

because there's n+1 cases, each one contributing n! (previous amount of permutations)

[dense creek]

hmm ok

I think I understand it now

Thank you!

[twilit matrix]

@dense creek are you in Ganapathi's class?

[dense creek]

yes

[twilit matrix]

nice lol

[dense creek]

lol

you too?

[twilit matrix]

yea

[lilac edge]

Define relation R on Z where xRy <=> x^2 + y^2 is an odd number OR y < 0
and proof whether it is reflexive, symmetric, antisymmetric, transitive

so my thought process is:
defining two relations, first - 2 does not divide x^2 +y^2
and the second one is x^2 + y^2 : y < 0

then examine both relations separately for each of reflexive, symmetric, antisymmetric, transitive

although I can drop the second condition when examining the reflexivity, since xRx does not include y value at all
is this a correct approach?

[stray reef]

no

[ivory badge]

x=y for xRx

So like

that’s a problem to throw out y

[stray reef]

it's rare that you can derive a property of $R_1 \cup R_2$ solely from the fact that $R_1$ and $R_2$ have this property individually

[vital dew]

Ann:

[ivory badge]

Also
Why split it up at all

[stray reef]

like

[lilac edge]

ok, so the relation should be then:
2 does not devide x^2 + y^2 : y < 0

and when examining xRx, only second x is < 0, right?

[stray reef]

....

what

the relation is "x^2 + y^2 is odd, OR y < 0"

and what do you mean by "only second x"

what second x

the two instances of the letter x refer to one and the same variable

[lilac edge]

when i am examing the reflexivity of the relation

[stray reef]

xRx is "2x^2 is odd OR x < 0"

which is clearly not satisfied by x=1

[lilac edge]

what i am not getting is the OR part
lets say we set x=1 as you said
and it is false for xRx
now I do have to set x = <0, so if for example, x = -1 would satisfy xRx, which it does not, but I want to understand this correctly, the relation would be reflexive

[stray reef]

no

a relation $R$ is called reflexive if and only if $(\forall x)(xRx)$

[vital dew]

Ann:

[stray reef]

so if there exists even one $x$ for which $xRx$ is false, then the relation is \textbf{NOT} reflexive.

[vital dew]

Ann:

[lilac edge]

sure, but since the domain has OR, does it mean that I have to examine for both conditions separately? so what i am saying is, 2 does not divide x^2+y^2 OR y<0, does it mean that there is two relations, first one 2 does not divide x^2+y^2 and the second one just x^2+y^2 where y<0, then xRx would be true in the second relation, since it does not care about if its odd or not

[stray reef]

"the domain has OR"

the domain is Z

it doesn't "have" OR or AND or any other logical connectives

the DEFINITION of your relation involves an OR.

do you understand that the statement "2x^2 is odd OR x < 0" is false if x = 1?

[lilac edge]

i dont, what does OR mean exactly then?

[stray reef]

OR means OR

do you not know the meaning of the english word "or"

[lilac edge]

yes

[stray reef]

you don't know what "or" means?

[lilac edge]

i do know what or means

[stray reef]

then why are you asking me what or means

if you already know what or means

[lilac edge]

i thought it represented logic here

[stray reef]

it is logical or

the statement "2*1^2 is odd OR 1 < 0". is it true or is it false

[lilac edge]

ok i get it now, thank you

[stray reef]

so you understand why your relation is not reflexive now?

[lilac edge]

yes, since there is at least one value for x, which gives even in my relation, it can not be reflexive

[stray reef]

ok well

can you check your relation for symmetry and transitivity yourself

[unreal berry]

Translation inbound*

Functions. Let the Amounts A ****** respective C b given. Create the function g.

(a) give an injective function f *** that makes h = becomes bijectiv

(b) same as above but A -> C does not become bijectiv

Please give me an explanation of how this works.

[weary tiger]

don't really know how to send you a picture but

@unreal berry draw blobs in a row of the 3 sets A,B,C

Like this but with A,B,C

Then from that you can see that you must map {1,2,3} to {a,b,d} or {b,c,d}

[unreal berry]

think I solved it

[weary tiger]

nice found a more relevant picture too

[unreal berry]

a) f = ((1,a),(2,b),(3,d))

[weary tiger]

yeh that works

[unreal berry]

b) f = ((1,a),(2,b),(3,c))

is this ok?

[weary tiger]

yeh

[unreal berry]

lol that was easy

[unreal berry]

*Translation inbound

Relations: Define the relation R on Z through

zRy <=> x^2 + y^2 is an odd number or y < 0

Give a complete summary or all capabilites of this relation; whether it is reflexiv, symmetrical, anti-symmetrical och transitiv. That means, if this relation does not have any of these properties, prove that it doesn't and vice versa.

Gonna write what I think they are trying to say and you can tell me if I am right or not

Reflexiv: Either x^2 + x^2 is odd or x < 0

is this correct thinking from me or not?

Transitive: x^2 + y^2 is odd or y < 0 Then y^2 + x^2 is odd or x<0

Anti-symmetrical: same as above and x = y

[stray reef]

"anti-transitive"

[unreal berry]

I might be suffering from serious brain injury and tinnitus

cus retarded people

Transitive: Either x^2 + y^2 is odd or y < 0 and Either y^2 + z^2 is odd or z < 0 then Either x^2 + z^2 is odd or z < 0

[stray reef]

you've listed out the statements whose truth you need to check. though you did not do so fully.

[unreal berry]

yeah

asking if my statements make sense before I test them.

[stray reef]

you forgot all your quantifiers

reflexive: (∀x)(2x^2 is odd or x < 0)
symmetric: (∀x)(∀y)[(x^2+y^2 is odd OR y < 0) => (y^2+x^2 is odd OR x < 0)]
transitive: (∀x)(∀y)(∀z)[(x^2+y^2 is odd OR y < 0) AND (y^2+z^2 is odd OR z < 0) => (x^2+z^2 is odd OR z < 0)]

[unreal berry]

why did you flip the less than?

you are using the left one

[stray reef]

oh

my bad, i misread the defn of the relation

[safe tinsel]

Sorry I haven’t read the conversation so I may be saying the same thing as Ann
But
Reflexive: xRx for all x
Symmetric: xRy implies yRx
Transitive: xRy yRz implies xRz

I think

[stray reef]

you are once again saying the exact same thing as me except that you only even mention a quantifier in reflexivity

[safe tinsel]

Lol

[unreal berry]

I get the quantifier

seems nice

[safe tinsel]

?

[unreal berry]

so does that mean only one of the the condition needs to be right?

I mean

the reflexive one is interesting since y isn't even included

[safe tinsel]

If R satisfies all of those 3 conditions, it’s an equivalence relation

Again, I’m pretty sure

[unreal berry]

then what if x = -1 y =-1 and z = -1

wouldn't R S AS T all be right?

[safe tinsel]

I’m confused

[unreal berry]

I mean

[safe tinsel]

If u are saying that = is an equivalence relation u are correct

[unreal berry]

Reflexiv: (xany)Either x^2 + x^2 is odd or x < 0 so just use -x

same with all the others.

[safe tinsel]

Ok what was the question sorry

I was just saying the definition of an equivalence relation in general

[unreal berry]

Ann am I correct to say all R S AS T are correct?

[safe tinsel]

What is R A AS T

[unreal berry]

sorry

Reflexive symmetrical anti symmetrical transitive

[safe tinsel]

Wth is anti symmetrical

[unreal berry]

same as symmetrical but x = y

[safe tinsel]

So xRx implies xRx?

That’s just a long winded version of transitivity

What was the actual question; why are we even talking about this

[unreal berry]

reflexive: (∀x)(x^2 + x^2 is odd or x < 0)
symmetric: (∀x)(∀y)[(x^2+y^2 is odd OR y < 0) => (y^2+x^2 is odd OR x < 0)]
transitive: (∀x)(∀y)(∀z)[(x^2+y^2 is odd OR y < 0) AND (y^2+z^2 is odd OR z < 0) => (x^2+z^2 is odd OR z < 0)]

@stray reef couldn't I just set all variables to -1 so that the right condition gets fulfilled?

[stray reef]

there's a difference between existential and universal quantifiers

you can't "set" a variable to anything when it's bound to a for all

[safe tinsel]

Exactly

[unreal berry]

???

[safe tinsel]

Unless u do a classic proof by example lmao

[unreal berry]

well x y z can always be -1 so I am ok

right?

[safe tinsel]

FORALL means not just a specific case

It means all cases

So also when x,y,z aren’t -1 and also when they are

[unreal berry]

:I

[safe tinsel]

😐

[stray reef]

do you know what "for all" means

evidently you do not

[safe tinsel]

Who?

[stray reef]

grallak

[unreal berry]

but if the right condition gets fulfilled then everything is ok right?

[stray reef]

no

[safe tinsel]

No

You must prove the FORALL part

[stray reef]

if you want to prove that R is reflexive.
then you need to make sure xRx is true for all x.

what part of "F O R A L L" do you not understand??????????????????????????

[safe tinsel]

Lmao

😐

B R U H

[unreal berry]

so any x could also be positive

[stray reef]

major bruh moment right here

[safe tinsel]

Yes

Like when u accidentally pmed me

[unreal berry]

x + x != odd

[safe tinsel]

That’s what ur tryna prove?

[unreal berry]

looking at the reflexiv

[safe tinsel]

???

@stray reef am I the only one who’s my name

[stray reef]

??

[unreal berry]

well x^2 + x^2 can never be odd if it's reflexiv

[stray reef]

anyway

grallak.

[unreal berry]

but it can be x < 0

[safe tinsel]

I meant confused

[stray reef]

you don't yet know if the statement (∀x)(2x^2 is odd OR x < 0) is true.

which

it should be obvious that it's not

[safe tinsel]

Bruh

[stray reef]

because if x=1

then neither of the two things connected by the OR

are true

they're both false

[safe tinsel]

2 times an integer is gonna be even May I point out

[stray reef]

so the entire thing is false

[unreal berry]

what if x is -1?

[stray reef]

so what if x is -1

[safe tinsel]

Still wrong

[stray reef]

this is a

FUCKING

FOR ALL

[unreal berry]

Are you sure about that?

[stray reef]

here's what you're saying rn

there's a room full of people

and you're insisting that all the people in there are white

[safe tinsel]

Lmaoooo

[stray reef]

and i point at one of them and say "look. john is black"

and you keep saying

[safe tinsel]

I see where this is going

[stray reef]

"but look here jack is white"

[safe tinsel]

Hahaha

[stray reef]

while pointing at another person

[safe tinsel]

Lmaooooo

That made me chuckle a lot

[unreal berry]

right I see your point

symmetrical

[safe tinsel]

Omg

What are u saying

[unreal berry]

all of these capabilities should be impossible then

well

actually symmetri is possible

anti-symmetri is also possible

no

actually not lol

Reflexiv is false, symmetry true, anti symmetri false cus if they are the same then they can't be odd

transitive should be possible

[stray reef]

symmetry is not true. 1R-1 is true but -1R1 is false

[unreal berry]

no

transitive should be false too

since odd + even = odd

even + odd = odd

[safe tinsel]

What are u talking about

[unreal berry]

odd + odd = even

[safe tinsel]

Yes we know

But why is that relevant

[unreal berry]

yeah you are right ann

[stray reef]

there is a counterexample to transitivity too

[unreal berry]

Reflexiv,symmetri,anti-symmetry,transitive are all false.

[stray reef]

1 R 2 and 2 R 3 but not 1 R 3

yes

this relation has none of those properties

[unreal berry]

Alright I see now

thanks.

👍

[safe tinsel]

And I still don’t know the question

[weary tiger]

Hi

How could I have figured out that this function is O(9^n) ?

Does any number raised to n that is greater than 2 and 3 work ?

If so, that means that in great O in an exponent, the coefficient of n is ignored, correct ?

[pale epoch]

$2^{3n+1} + 3^{2n+2} = 2\cdot2^{3n} + 3^2\cdot3^{2n} = 3\cdot2^{3^n} + 9\cdot3^{2^n} = 3\cdot8^n + 9\cdot9^n$

[vital dew]

Lochverstärker:

[pale epoch]

convince yourself that this is true

and then that the result follows from that

[obtuse lance]

that 3rd part looks fishy

ah I think I see what you meant to do

[pale epoch]

it's correct modulo typos

feel free to correct

[obtuse lance]

$ 3\cdot(2^3)^n + 9\cdot(3^2)^n$

[vital dew]

Merosity:

[obtuse lance]

this is what you meant in your 3rd part, not the exponentiated exponents

[pale epoch]

oh

you are absolutely right

[obtuse lance]

anyways proceed @weary tiger

[weary tiger]

so since the last part is 3 * 8^n + 9 * 9^n

we can drop the 3 * and the 9 *

and then pick the fastest growing of 8^n and 9^n

and that's the answer

[pale epoch]

essentially

[weary tiger]

why essentially ?

[pale epoch]

it's not a rigorous argument

[weary tiger]

Ah, right

Well I'm glad you showed me that technique, I was just eyeballing previously

so thx

[pale epoch]

that last equal signs is iffy, but yeah

[safe tinsel]

iFfY?

Bro

[unreal berry]

is the amounts of words you can write with KOMBINATORIK = 12!/(2! X 2! X 2!) ?

just quick check

[stray reef]

don't use X for multiplication

other than that, yes

[safe tinsel]

Lol

[weary tiger]

can someone explain to me why the assignment of result is 2?

for time complexity

[sacred furnace]

f:Z x Z -> Z , f(a,b)= |a-b|

How do I determine whether this one-to-one, onto, both, or neither?

[heavy tinsel]

@sacred furnace try to fix b to 0

like f(a,0) = |a-0| = |a|

|a| >= 0, so it cant be negative

which means it cant cover the codomain, Z, which means its not onto

i think..

as for one-to-one,

fix b = 0, then f(1,0) = |1 - 0| = |1| = 1 f(-1,0)

so its neither

im also a student and we covered the same topic a month ago so correct me if you think i made a mistake

[sacred furnace]

This is helpful, I just am having such a hard time with this course, I probably should have dropped it ages ago, this subject is so dry and dense I can hardly wrap my mind around it

So hard to find good help to, I feel I need a tutor but don't know where to find one

[heavy tinsel]

i know how you feel exactly, i took this course only because it is required to get into the comp sci program at my school

[sacred furnace]

Book sucks, teacher sucks

Same

[heavy tinsel]

well, for me i try to understand the proofs in my textbook, then proceed to do as many questions as i can related to the topic

so far im doing ok in the course, i dont see any other way around it

[dapper mason]

For my base case: n=1, 15|15

My induction hypothesis: there exists k in the set of positive integers such that k is odd and 15|4^n+5^n+6^n

In my induction step: n=k+2. k is odd so there exists an integer a such that 2a+1 = k so from my induction hypothesis I have 4^(2a+3)+5^(2a+3)+6^(2a+3)

I think I'm in the right path but I'm not sure what algebra to do next

<@&286206848099549185>

[near prawn]

theres no need to re write k like that

4^(k+2)+5^(k+2)+6^(k+2)=16x4^k+25x5^k+36x6^k=16[4^k+5^k+6^k]+9x5^k+20x6^k

@dapper mason

[distant bay]

ayo, anyone here self studying Discrete Maths and if so what books / courses you following

[near prawn]

using rosen rn

[distant bay]

having a look through it now

can't seem to see the requirements anywhere

[near prawn]

there arent any really

just make sure youre familiar with the all formalities i guess

like sets, functions, relations etc

[pale epoch]

no

what is your definition of graph

so yeah, count what's the total amount of edges possible

and then for each edge, you have 2 choices: either include it in the graph or not

this gives you 2^(something) total graphs

depending on how many possible edges there are

there is more than 4 possible edges in this case though

and depending on what distinct means in this case, you also have to check for isomorphisms 🤔

[obtuse lance]

what do you mean "allowed"

either you're counting graphs as if they're labeled or you aren't

like imagine the graph with vertices A and B connected and C and D connected

this is distinct from A and C connected and B and D connected

however, they're isomorphic as graphs if you are counting instead by ignoring the labeling

so they are the same graph from that perspective

[obtuse lance]

the image of the text clears it up

for the graphs to be distinct, they can be isomorphic

https://prnt.sc/ryli9i

the red graph is distinct from the green graph

but they're isomorphic

so when you have 4 vertices

how many edges can you have at most?

good

so now to count the number of possible graphs you think

either it has an edge here, or it doesn't

yeah

in general while we're here

I was gonna ask what's the number of graphs when you have n vertices

try to see if you can make it planar or not first

and tell me your guess

show a picture to prove it

well to be planar just means something very simple

you can draw it without the edges crossing

I can just look lol

yeah

proving it's not planar is trickier

no not true

now you've cut it apart

I'm assuming you meant specifically https://gyazo.com/8462ffa91d898f7c97ee2f0ee4149f2a

that you sent earlier

see in the middle it crosses

you can rearrange vertices in space but you can't chop them

that graph has 3 edges at every vertex

your red graph doesn't

so they're obviously different graphs

yeah nice

here was my solution I was gonna send

https://prnt.sc/rylpha

no it's not the only way

there's a theorem I forget the name

kurtowski something

[pale epoch]

kuratowski

[obtuse lance]

I don't know if that is sufficient to use that formula

yeah you'd already know it has faces by that point

I guess that tells you how many faces you have to look for

but that's not quite enough

[pale epoch]

kuratowskis theorem is fine for mathematical needs

but in reality there are better algorithms to check if a graph is planar

[obtuse lance]

it's like 2 kinds of "sub"graphs

not sure what the terminology is

well been a while since I thought about this and I never learned the proof, just know there are the two graphs to search for

I think K_3,3 and some fancy star one that's popular

[pale epoch]

K_5 and K_3,3 are in some sense the "smallest" non-planar graphs, yeah

[obtuse lance]

back to the original question before, you should probably know how to find

what's the number of graphs when you have n vertices

well I'll let you both play I'm heading out

I have to go do boring stuff 😢 have fun

[pale epoch]

🤷

K_n is the graph with n vertices and the maximum amount of edges

$K_{n,m}$ is something called a bipartite graph with maximum amount of edges, which you will probably encounter in the future

[vital dew]

Lochverstärker:

[north jewel]

is it natural to want to prove everything by contradiction?

i.e. to me proving something like $A \neq B$ for
$$
A = { 1, 2 }, B = {x | x^3 - 2x^2 - x + 2 = 0}
$$
seems most natural by using contradiction

since it follows logically from the definitely of set equality

[vital dew]

Frank:

[north jewel]

like how would I even nicely prove this directly without contradiction?

[pale epoch]

how do you even prove this with contradiction

[north jewel]

assume A = B, then for all y in B, y in A

y = -1 is in B, which is not in A

contradiction squiggle

[pale epoch]

why did you assume A = B

[north jewel]

for purposes of contradiction

it feels more robust this way idk

[pale epoch]

exactly

just don't assume it

you found an element that is in B and not in A

proof done

this is not a contradiction proof

[north jewel]

something about that doesnt feel right

i think im just being really stupid rn lemme think lol

hmm ok i guess

i would just have to establish that if A != B then there exists some y in A s.t. y not in B

none of my profs examples used this which is probably why

[pale epoch]

i mean that is just what A != B means

[north jewel]

yea

but he only defined A = B for us lol

[pale epoch]

yes, but you can just negate that

[north jewel]

so would the negation of
$$
\forall x \in X \Rightarrow x \in Y
$$
be
$$
\exists x \in X \text{ where } x \not\in Y
$$

[vital dew]

Frank:

[pale epoch]

eh

the negation of $\forall x: x\in X \implies x \in Y$ is $\exists x: x\in X \land x \notin Y$

[vital dew]

Lochverstärker:

[north jewel]

o_o

whats the ^ mean

[pale epoch]

and

[north jewel]

ah i see

how do you logically construct this negation

[pale epoch]

notice that this is not the negation of X = Y tho

the original statement is $X \subseteq Y$

[vital dew]

Lochverstärker:

[pale epoch]

so the negation is just the negation of that

[north jewel]

yea negation of X = Y would be neg(X subset Y) or neg(Y subset X)

[pale epoch]

yeah

constructing negations of logical statements you can just look up

it basically turns for alls into exists

ands to ors

and sth like that

[north jewel]

ok i see

thanks

[weary tiger]

There are 5 courses A B C D E and 3 of them must be scheduled at 2pm, 4pm, 6pm how many schedules are possible

is this 5 choose 3?

or 5 * 4 * 3 or something i dont get what its asking

[north jewel]

it would be a permutation since order matters

ABC (2pm, 4pm ,6pm) is different from BAC

5 choose 3 is the # of ways you can choose 3 elements disregarding order

[weary tiger]

ok so P(5, 3)?

that ends up being 5 * 4 * 3 which is what i thought it was initially

[weary tiger]

A company has 10 software projects and 3 software engineers and wants to assign one project to each engineer, how many assignments are possible?
is this P(10, 3)?

[echo karma]

can anyone help me with these proofs
my professor didn't teach this and i am struggling with it
Prove the following statements:

1. Any three consecutive integers will include a number divisible by 3.
2. If a and b are rational numbers, with b ≠ 0, and r is an irrational number, then a + br is irrational.
3. 8^n-3^n is divisible by 5 for any integer n>= 0

i get the first one but am not sure about the other two

[near prawn]

what did u try for them

@echo karma

[white jetty]

Hey guys

I got confused by a question

So suppose A={1, 2, 3} and B={a, b, c, d}
Is there a function from A to B that is onto?

[pale epoch]

what do you think?

[white jetty]

I think yes

[pale epoch]

that is not a function though

[white jetty]

I guess that's what I got confused

😂

[pale epoch]

it's only a function if for every input value you have a unique output value

in this case for 3 you don't have that

[white jetty]

Ohh

In order for it to be a function....okay that make sense

thanks man @pale epoch

[pale epoch]

you're welcome

[boreal beacon]

why does this graph have a subdivison of k3.3

[weary tiger]

@boreal beacon if you remove 8 and 4 and combine 781 into one edge and 345 into one edge then it's k3,3

Also not that it really matters but i'm p sure you'd say that this graph is a subdision of K3,3 not it has a subdivision of K3,3

[boreal beacon]

oh ok thankyou

[north jewel]

With mathematical induction, you need to show that if the statement is true for n = k, it is also true for n = k + 1. Are you also allowed to assume the statements where (basis) < n < k are true?

[gleaming zephyr]

it works too

[north jewel]

ok

[gleaming zephyr]

thats complete induction

or strong induction

[echo abyss]

Suppose $A = {a,b, c,d}$ and $R ={(a,a),(b,b),(c, c),(d,d)}$. Is R reflexive? Symmetric? Transitive? If a property does not hold, say why

[vital dew]

DSO:

[echo abyss]

For the symmetric property since xRy is false then xRy => yRx is true

Is that all that is needed to show that property is present?

[north jewel]

yea thats the definition of symmetric right

[echo abyss]

Yeah I'm just having difficulty putting that in a more "mathy" way

If that makes sense

[north jewel]

hmm.. well idk if im much help since im also just learning this but I would do something like
We need to show that for all x, y s.t. xRy => yRx. then just go case by case, there's only 4 possibilities for x,y anyway

idk someone else should confirm/give a better way

[echo abyss]

Okay thanks

[weary tiger]

It's clearly all 3

[echo abyss]

Yeah I can see that I'm just having difficulty saying as to why that is

[weary tiger]

So $\forall x \in A$ we have that $(x,x)\in R$

[vital dew]

same:

[weary tiger]

which means that it's reflexive

[echo abyss]

Okay

[weary tiger]

$(x,y)\in R \implies (y,x) \in R$ clearly too

[vital dew]

same:

[weary tiger]

as the only shit that is in R is of the form (x,x)

so it's symmetric

[echo abyss]

Oh okay

I didn't realize I could simply just say that

$(x,y)\in R \implies (y,x) \in R$

[weary tiger]

i mean theres not really much you can say

[vital dew]

DSO:

[echo abyss]

Yeah

[weary tiger]

that's the definition of symmetric

but ofc you need a forall a

at the start

but i mean it's just the identity relation and all of the properties are kinda trivial

[echo abyss]

It just seemed to simple to just basically restate that def

[weary tiger]

the question only asks to explain why they don't work

but they do

so i dont even really think it wants you to say much

[echo abyss]

Yeah our prof said to also say why they do

[weary tiger]

but you can go through and manually check all properties too

[echo abyss]

Okay that makes sense

[weary tiger]

like you can check that R is reflective by looking at all elements

you can check that its symmetric by looking at all the elements too

then you can explain that it's transitive too by looking at it

[echo abyss]

yeah

Alright thanks

[gentle frost]

Assuming you can use uppercase letters and digits 0-9.
"How many different 7-character license plates avoid having 2 digits in a row?"
A classmate of mine told me i can find a recurrence relation, but im having some trouble

[weary tiger]

@gentle frost how do license plates work lol

whats the format

[gentle frost]

you can use uppercase letters and digits 0-9

[weary tiger]

and its just a 7 digit string of any of them?

because then you have 36 choices of characters

and each one has to be different to the one before

[gentle frost]

yea

[weary tiger]

so there's

36*35*35*... possibilities

=36*35^6

the recurrence relation would literally be u_{n+1} = 35*u_n but is kinda pointless

[gentle frost]

hmmm, i remember getting the same answer, but was told i was wrong, im trying to remember why

you can't have 2 of the same numbers, but you can have 2 of the same letters.

AAAAAAA is valid

A1A1A1A is also valid

like if the first character is A, then for the next spot i should be able to use any of the 36 different possibilities

but im limited to 35 by that answer

[weary tiger]

Ah okay I just assumed nothing could be repeated

well if you let u_n be the sequences with n characters that end in a number and v_n be the sequences with n characters that end in a letter

then u_1=10 and v_1=26

and we have u_{n+1}=9u_n+10v_n

and v_{n+1}=26u_n+26v_n

and the number you want is v_7+u_7

you can solve the recurrence relations simultaneously to get an answer

[gentle frost]

ok, how did you get those 2 eq. not sure i follow

for a license plate 2-characters long:
if the first character is a number, then you have 35 possibilities for the second character
if the second character is a letter, then you have 36 possibilities for the second character

[weary tiger]

so

we are looking at the n+1th character

for u_{n+1} we are considering when that character is a number

in the case of the nth character being a number there are 9 possibilities

in the case of the nth character being a letter there are 10 possibilities

for v_{n+1} we are considering when the n+1th character is a letter

and in both cases there are 26 choices

[gentle frost]

yes

[weary tiger]

and the total sequences is v_n+u_n

since they must end in either a letter or number

[gentle frost]

for v_{n+1} we are considering when its a ltter
ok. im trying to process this actually. lol. im slow at understanding things

[weary tiger]

im gonna go to sleep but idk what best way is to solve simultaneous recurrence relations like that but one way is you could just make it into a matrix equation that should be simple enough

[gentle frost]

ok thank you!

[weary tiger]

Can someone provide me a proof of Chapman kolmogorov equation proof. The proof has been left as an exercise in the book but i can't figure it out

[lyric pumice]

@gentle frost @weary tiger Here is a formula for a generalized version of the problem, where a string of n characters is made by choosing from a set of a numbers and from a set of b letters.

[gentle frost]

oh yeah, thank you. I figured out a simpler recurrence relation actually

[vital dew]

tekunalogy:

[lyric pumice]

@gentle frost @weary tiger I fixed a minor mistake in the formula.

[gentle frost]

oh thank you!

[stray reef]

let D(G) be the highest degree of the vertices in G

then by definition for every vertex v you have deg(v) <= D(G)

sum this up over all vertices of G and you have the inequality you asked about

sum this up over all vertices of G

the left hand side becomes the sum of all the degrees

the right hand side becomes the sum of |V| copies of D(G)

[stray reef]

no, it's the sum of |V| copies of the highest degree

[analog sonnet]

(1, 2) and (2, 3) are in there, but I don't see a (1, 3)

np

[weary tiger]

7^2 = 49 which is 24 mod 25 which is -1 mod 25

[obtuse lance]

I mentally would just go straight from 49 = 50-1

[distant bay]

I'm guessing most of the people in this room are here studying this for computer science right ?

ahhh

yeah, the moment I got out of uni, Computer Science got a ton more interesting

just because I could literally take it anywhere at my own pace

like even now, I'm just studying maths to buff up my development skills

yeah yeah, I work as a web developer

no not really for your average gig

but for high end jobs, it gets brought up a lot more

plus I wanna do games development

oh yeah you'll definitely need maths for those

I know that you need Linear Algebra for AI work

huh never heard of it anywhere before

what's the application if you don't mind me asking ?

ah ok

honestly I'm just making my way though the basics on Khan Academy at the moment as there were major hole in my maths understanding

so haven't touch discrete maths :/

hoping to get to it, this whole thing is going on

oft, that's rough

[weary tiger]

Let $H(V,E')$ be a subgraph of $G(V,E)$ that is minimally connected. Assume $\delta(H)\geq2$ then $e(H)\geq|H| \implies f \geq 2$ by Euler's formula. So there is a cycle which is a contradiction as $H$ minimally connected so $\delta(H)=1$. $\exists v$ s.t $d(v)=1$. Then $H-v$ is still connected hence $G-v$ is connected

[vital dew]

same:

[weary tiger]

Does that make sense

or should i also explain why H-v is connected and that implies that G-v is connected?

[languid heart]

Is there anyone experienced with RSA algo?

[past plaza]

@languid heart I am not and I'm looking for good review videos on that if you have anything please lmk

[boreal beacon]

does anyone know the formula for this question? I cant find it

[obtuse lance]

yeah it's the multinomial coefficient

like the literal term is

$\frac{9!}{3!5!1!} x^3 (2y)^5 z^1$

[vital dew]

Merosity:

[obtuse lance]

so they pull the coefficient off that, if you want to literally derive this you can do it by thinking combinatorially like you would for the binomial coefficients

depending on what you think is hard determines how I explain it any further than that but at least you have a keyword to google on your own time

[boreal beacon]

ok

thankys

[weary tiger]

just to check

13=xmod7

x would be equal to 20 right?

since 13 and 20, are in the same equalivence class

meaning they both have have the same remainder of 6

[faint narwhal]

there are a lot of things you can pick for x

20 works, so does 13, so does 6

[weary tiger]

but the smallest one would actually be 6 right?

yeah so it would be 6

cool

[north jewel]

Can someone critique my proof? (iii)

[weary tiger]

seems fine

[north jewel]

ok ty

[boreal beacon]

whats the equation for this?

is it

[near prawn]

yes

[lyric pumice]

@boreal beacon That is not an equation.

[boreal beacon]

i dont know what the correct terminology is xd

[lyric pumice]

It is an expression that is a multinomial coefficient.

[faint narwhal]

Yeah, this is the hockey stick identity

[boreal beacon]

for part C, why would the answer not be

nvm i figured it out

[ancient basin]

Would like to know if my work for this question (b,c,d,e) is correct. I'm still iffy about the theory, so I feel I may have done some conceptual mistake.

[lyric pumice]

@ancient basin Connect 1 and 9.

[ancient basin]

Alright, thanks!

[ancient basin]

I think my upper/lower greatest lower/least upper bounds may be wrong. Still trying to grasp what the right answer is

[stray reef]

have you learned about modular inverses yet

you're glossing over way too much detail here

...

gcd(7,25) = 1 means that the inverse of 7 mod 25 EXISTS

there are many ways

if you know how to solve diophantine equations you may find it helpful to look at the equation that way

trial and error

reduce -77 mod 25 obviously

or i mean

you could just write -77 itself but that's too big

so mb go with -2 instead

is -2 not an integer all of a sudden

we could

i just don't like large numbers

[stray reef]

no

neither of these two is a subset of the other

yes, {1,2} is a proper subset of {1,2,3}

but {1,2} and {1,2,3} do not have the same cardinality

[stray reef]

sure that works

[lunar remnant]

Hey guys what would be the next two numbers after 2,88,80,16,11,3,30,95 and why

[stray reef]

19 and 19

by the fundamental theorem of malicious compliance with underspecification

[weary tiger]

@lunar remnant 87,44 maybe

but its not really maths

[lunar remnant]

oop yeah, I browsed through that page as-well haha

[lilac edge]

SANNOLIKHETSLARAN

a) probability of drawing two of the same letters, (also two S or two N)
b) if two letters are the same, what is the probability of them being two S
c) if two letters are the same, what is the probability of them being two N

a) ((2 over 1) * (3 over 1)) / (17 over 2)
b) 2/17 * 1/16
c) 3/17 * 2/16

is this correct?

[mossy sable]

I have a recursive relation, f(x) = f(x-1)*x + f(x-2)*x^2 (I wrote it to be more friendly for discord, but f(x) is actually a sub n)

How do I find f(1000)?

I'm thinking I need to get an explicit formula, but I have no idea how to go about that, and google hasn't been much help

[weary tiger]

Search for homogenous difference equations, might help, there were ways to find an explicit formula.

[mossy sable]

Alright

[weary tiger]

@mossy sable you'll need ICs surely?

[mossy sable]

What is an IC?

[weary tiger]

initial condition

[mossy sable]

Oh right

a(0) and a(1) are both 1

I thought I wrote them there, but I guess I didn't

Frankly I've written this question in so many places it's hard to keep track

It looks a LOT like the recursive formula for the fibonacci sequence

[weary tiger]

how would i go about this

[pale epoch]

did you cover the master theorem?

[weary tiger]

yes i believe so

[pale epoch]

then use that

[vocal forum]

hey all, im trying to do a proof via induction, this is what i have so far: http://prntscr.com/s03drh

however im stuck, I cant seem to complete the LHS to equal the RHS

my question is whether i need to add (k+1)^2+1 on the RHS side as well. Or if I just simply missed a step

[pale epoch]

you have 2 mistakes i think

one you fix by ignoring

[vocal forum]

ya i just found one

[pale epoch]

the other causes your error

[vocal forum]

didnt add k+1 on the RHS for the first k

which is the other error?

[pale epoch]

there is a stray +1 on the LHS in line 4

k^2 + 1 +...

i don't think that should be there?

[vocal forum]

http://prntscr.com/s03lhu

is that the one you are talking about?

[pale epoch]

nah

but i might be wrong

[vocal forum]

is that not from: http://prntscr.com/s03md0

[pale epoch]

yeah, you are right

i just didn't get the rule for the summands

[vocal forum]

all good

[pale epoch]

anyways, with (k+1) what you did checks out

[vocal forum]

(k^3+6k^2+11k+6)/3

[pale epoch]

altho you should add $\iff$ or something in front of every line

[vital dew]

Lochverstärker:

[pale epoch]

or just start with the LHS and dedue the RHS

[vocal forum]

ok ya

[pale epoch]

otherwise the very first line is what you want to show

[vocal forum]

http://prntscr.com/s03qmm

LHS doesnt equal RHS :/

i know im just missing something lol

[boreal beacon]

is the dual of every planar graph isomorphic to its original planar graph

[pale epoch]

ehh

the original statement you are trying to prove is wrong @vocal forum

[vocal forum]

as in it cannot be answered

?

[pale epoch]

try n=2

[vocal forum]

in my base case?

[pale epoch]

yeah

[vocal forum]

http://prntscr.com/s04442

thats actually a 2

so n=1 still works

thats mb

[pale epoch]

yeah ok but

$2 + 5 = 7 \neq 8 = \frac{2\cdot3\cdot4}{3}$

[vital dew]

Lochverstärker:

[vocal forum]

ahhhhh

[pale epoch]

you cannot prove a wrong theorem

so this is to be expected

[vocal forum]

ok it cant be answered?

you got me confused lmaoo

[pale epoch]

the very first line

the thing you are trying to prove

is incorrect

[vocal forum]

lmao

thank you

[bleak cypress]

Can anyone please help

With discrete math

[lyric pumice]

@bleak cypress #❓how-to-get-help

[bleak cypress]

Yes i have question

please help with these reviews

@lyric pumice

[rough copper]

It's not fair to go: please help with these reviews

What have you done

Show us some will to do it

And we will help if we can

[limpid berry]

plz. made the wroshian matrix thing

[sour arrow]

Show that they are both solutions, show that they are linearly independent. Wronskian may be one way to do so.

@limpid berry

ax + bxln(x) = 0
Only has a solution when x = e^(-a/b). Since we can't fix x, there's no a and b that always satisifes this

[patent oriole]

(S1) ∀x(Q(x) ↔️ R(x))
(S2) ∃x(Q(x) ∧ ¬R(x))
(S3) ∀xQ(x) ↔️ ∀xR(x)
Are the following true or false?
Every interpretation that makes (S3) true also makes (S1) true.
Can anyone help?

[distant bay]

heya all, just wondering what's your opinion on Trevtutor's course on discrete math ?

https://www.youtube.com/watch?v=tyDKR4FG3Yw&list=PLDDGPdw7e6Ag1EIznZ-m-qXu4XX3A0cIz

https://www.youtube.com/watch?v=DBugSTeX1zw&list=PLDDGPdw7e6Aj0amDsYInT_8p6xTSTGEi2

[night crescent]

Hey guys, lets say I have a set {1,c,8,8,c}

Does it matter if I said that {8,8,c} or {c,8,8} is a subset of that set?
Futhermore, does the order matter?

[pale epoch]

{1,c,8,8,c} = {1,8,c} and {8,8,c} = {8, c} = {c, 8, 8}

[sleek swallow]

@night crescent There's no notion of ordering or repetitions in a set. So, like Loch said above, {8,8,c} = {8,c}

[quartz gull]

Can someone help me with this?

[weary tiger]

P(a)+P(b)+P(c)=1

P(a,c)=P(a)+P(c)

can you work it out from there

[quartz gull]

@weary tiger

[weary tiger]

yee

[quartz gull]

thanks

[weary tiger]

y did u delete

lol

[weary tiger]

the characteristic equation here is r^3+6r^2+9r+4=0 ?

[stray reef]

yes

[weary tiger]

Ok thx

I'm not getting the right sequence at the end once I've solved

I'm getting that the solution is f(n) = 3(-1)^n + -1(-4)^n

I have the following roots: r1 = -1 with multiplicity 2

and r2 = -4 with multiplicity 1

f(n) is giving {2, 1, -13, 61, ...}

a(n) is giving {2, 1, 0, -17, 98, ...}

[stray reef]

your general solution is $a_n = (c_1 + c_2n)(-1)^n + c_3 (-4)^n$

[vital dew]

Ann:

[weary tiger]

How come, because there is a root with multiplicity 2 ?

but thank you

[stray reef]

yes for exactly that reason

[weary tiger]

Can anyone help

[stray reef]

what's giving you trouble here

[weary tiger]

What method do i use?

I tried prime factorization and got nowhere

[stray reef]

write out the definitions of everything

[weary tiger]

I did

heres my work that got me nowhere

[stray reef]

,rccw

[stray reef]

no

[weary tiger]

I also tried just writing ka=bc and stuff

[stray reef]

the definition of divisibility has nothing per se to do with prime factorization

yes that is what i am trying to suggest

$a | bc \iff (\exists k)(bc = ka) \ \gcd(a,b) | c \iff (\exists m)(c = m \gcd(a,b))$

[vital dew]

Ann:

[weary tiger]

yea I tried that as well

like i wrote the definitions down

[stray reef]

note that by bézout's lemma we have $(\exists x)(\exists y)(\gcd(a,b) = xa + yb)$

[vital dew]

Ann:

[weary tiger]

ohhh

bezout

fuck i didnt think of that

thanks

im so dissapointed

@stray reef

is it possible to do it by prime factorization definition of integers

[stray reef]

prime factorization isn't a definition

anyway

[weary tiger]

like notation

[stray reef]

okay, let $a = \prod_p p^{\alpha_p}$, $b = \prod_p p^{\beta_p}$ and $c = \prod_p p^{\gamma_p}$ where all three products are to be taken over the primes

[vital dew]

Ann:

[stray reef]

and α_p, β_p, γ_p ≥ 0 obviously

[weary tiger]

yep

[stray reef]

$\frac{bc}{a} = \prod_p p^{\beta_p + \gamma_p - \alpha_p}$

[vital dew]

Ann:

[stray reef]

$\frac{c}{\gcd(a,b)} = \prod_p p^{\gamma_p - \min(\alpha_p, \beta_p)}$

[weary tiger]

Oh i made a mistake

yea

[vital dew]

Ann:

[weary tiger]

man...

I made a careless mistake in writing this out

[stray reef]

we want to show that $\frac{c^2}{a} = \prod_p p^{2\gamma_p - \alpha_p}$ is an integer

[vital dew]

Ann:

[weary tiger]

where 2Yp-Ap>= 0 right

[stray reef]

gamma_p

[weary tiger]

for all p

[stray reef]

but yes

[weary tiger]

ok

thanks for the help, ill try again w/ both methods

wait actually i didn't make a mistake writing it out

[vital dew]

LHC2012:

[weary tiger]

and we have $\gamma_{p}- min(\alpha_{p}, \beta_{p}) \geq 0$

[vital dew]

LHC2012:

[weary tiger]

but then i couldnt show the 3rd

[stray reef]

$\alpha_p \geq \min(\alpha_p, \beta_p)$

[quartz gull]

yo @stray reef is your left hand okay?

[vital dew]

Ann:

[weary tiger]

yeap i recognize that, but i couldnt use it

[quartz gull]

I heard you got hurt while playing basketball

[stray reef]

what

are you confusing me with someone else

[quartz gull]

nope someone told me about u lol

[stray reef]

who

i don't even play basketball

[quartz gull]

are you fine though?

[stray reef]

i am okay and so is my left hand

[quartz gull]

oh great then do my homework 😆

[stray reef]

....what

[weary tiger]

hes doing a test or smthg lol

[stray reef]

<@&268886789983436800>

[weary tiger]

thanks Ann

lmfao sneaking 100

@weary tiger don't post DMs please

mb

np dw

so given say $b+c-a \geq 0$ and $c-min(a,b) \geq 0$, and knowing $a,b \geq min(a,b)$, I still can't show $2c-a\geq 0$

[vital dew]

LHC2012:

[weary tiger]

@stray reef if you could help again

This is wrong

[stray reef]

is it

[weary tiger]

as a counter-example: take a=b=-4

and c=-3

is it
If I'm not mistaken

ah yes, restrict it for positive values

[stray reef]

a, b and c are nonnegative integers here

[quartz gull]

^^^true

[stray reef]

hmmmm

[weary tiger]

oh sorry didn't know that

[sudden knot]

do cases

a≥b, a<b

or something like that

[wet belfry]

what does AVI stand for in discrete mathematics ?

[wet belfry]

because I keep searching for it but nothing to find, it seems it's like that our professor invented it 😅

[pale epoch]

ask him then

[lilac gazelle]

can someone tell me the difference between (m+n) mod p and m+n (mod p) if there is one

[faint narwhal]

there's not

[lilac gazelle]

oki ty

[quartz gull]

Hey can anyone help me with discrete?

[near prawn]

[quartz gull]

@radiant bough Is your hand okay? I heard u got hurt while playing baskeball

[radiant bough]

uhhhhhh what

[quartz gull]

is your hand okay?

[radiant bough]

there are a dozen bunchos in here

are you sure you have the right one

[quartz gull]

yes i think but is your hand okay?

[radiant bough]

you might be sure but I am not

[quartz gull]

If your hand is fine then do my homework @radiant bough

😆

lol

[lilac gazelle]

🤔

[radiant bough]

I didn't even walk into that one

[quartz gull]

hahah i was trying to be funny

i don't have any homework lol

😆

[lilac gazelle]

in that case may I ask a question

[quartz gull]

Sure go ahead

[lilac gazelle]

if m is congruent to n (mod p)

does that mean n is congruent to m (mod p)

[quartz gull]

yes

it is

[lilac gazelle]

POG, ty

[quartz gull]

hahaha😆 u got me

nice one

[lilac gazelle]

[quartz gull]

I am so bored coz this Corona

when will this end :/

I am so unmotivated as cs major

[lilac gazelle]

do you play basketball

[quartz gull]

nope

I play soccer

[lilac gazelle]

do your quads hurt

alright I'm out

[quartz gull]

hahaha

nice one

😆

[lilac gazelle]

the cringe is too much, I gotta take a break from life

what has quarantine done to me

[quartz gull]

i feel same

I am like trying to play pranks now instead of focusing on my school work lol

[lilac gazelle]

me:
silently sifting through discrete math textbook cause why not

[quartz gull]

damn i am motivated now

[lilac gazelle]

see now I understand why m + n is congruent to m mod p + n mod p (mod p)

since m ≅ n mod p --> n ≅ m mod p

that means (m + n) mod p ≅ m mod p + n mod p -----> m + n ≅ m mod p + n mod p (mod p)

THEOREM UNDERSTOOD

[slate marten]

i got a word problem that i could use some help with, is it okay if i post it in here

[sour arrow]

Ya

How many sets of 5 coins can you choose without the penny restriction?

[slate marten]

C(12,5) ?

[raw birch]

You have 5 ways of selecting the compulsory penny. When you take it, you have 4 pennies and 7 nickles and you have yo select the other 4. So the result is 5 times that number

C(12,5) ?
@slate marten Pennies and Nickels are different so be careful

Well, I think that wouldn't matter here

[sour arrow]

This problem is combinations with repetition. There's 2 objects to choose from, and you choose 5 of them. That's (2 + 5 - 1)C5 ways

[raw birch]

So it does

[sterile flint]

Can someone explain this process for me?

How does that become that

[slate marten]

hmm