discrete-math

[latent cloud]

Hm okay. So here P is AvB?

But why can he just add vB to A?

[vale cairn]

That's just because like of this

If A is true, then either A is true or B is true

[latent cloud]

Okay. So is this a correct way to solve this problem?:```
Show that A → B ∨ C is a logical consequence of A → B and B ∨ D → C
(1) A -> B (premise)
(2) B v D -> C (premise)
(3) A -> B v D (from 1 since A -> B still holds independent of D)
(4) A -> C (Hypothetical syllogism from 3)
(5) A -> B v C (from 4)

[vale cairn]

I'm basically unsure what counts for you or not

[latent cloud]

does that show that A → B ∨ C is a logical consequence of A → B and B ∨ D → C?

[vale cairn]

Oh I meant like I'm unsure what level of rigour is expected / what stuff you can assume

I would write it out a bit differently though

Like, I'd expand on why A -> B implies A -> B v D

You can add another step or two for that

Well

So like

You went from A -> B to A -> B v D

But if you can make that leap, you might as well make the leap from A -> B to A -> B v C

and be done

[latent cloud]

Okay. But how do you show that a statement is a logical consequence of some other statements? Is it just by showing that A → B and B ∨ D → C together becomes A → B ∨ C?

[vale cairn]

Well not "becomes" but yeah you can derive A -> B v C from the other two using modus ponens (and intermediate steps as above)

In fact the B v D -> C is unnecessary

Like, A -> B v C is a logical consequence of A -> B

[latent cloud]

But I have to show that it is a logical consequence of BOTH A → B and B ∨ D → C, no?

[latent cloud]

I'm not using modus ponens, where should ive use it?

[civic lava]

Can some please help me with this? I've been trying to get it for hours and I have no idea what to do😭

[fallen kettle]

this is math? 😨

[civic lava]

Yes

Discrete math

[sage creek]

Start with the smallest unequal length strings and then generate all unequal length strings from those?

[final swift]

Hello everyone, our teacher gave us the following to determine whether is a function or not. Let $$ f: \mathbb{Z} \to \mathbb{Z} \text{ where f(x) is defined as } f(x) =\bigg (\sqrt{(x-9)}\bigg)^2$$. She told us that the answer is not a function and her counterexample was $$f(-1) = \bigg(\sqrt{(-1-10)}\bigg)^2 \not \in \mathbb{Z}$$. She further mentioned that we cannot just simplify because we can see the imaginary number coming up. However, I'm not convinced with the argument because we have the rule of imaginary numbers that says $$i^2 = -1$$. So the counterexample would result to $$f(-1) = \bigg(\sqrt{(-10)}\bigg)^2 = 10i^2 = -10 \in \mathbb{Z}$$ and in fact, I can see that $f$ is function. Am I right to assume that $$10 \in \mathbb{Z}$$? I might be missing some key concepts here which is why I'm not getting the same answer as hers. Thank you.

[vital dew]

ssrrll

[coral parcel]

You'll probably need to divide into cases such as:
a) n+m < k
b) m <= k < n+m
c) 0 <= k <= m
Each of theses should be relatively easy to write a grammar for. Then you can just put them together with a top-level S ::= A | B | C

[next sail]

Given that x is a predicate variable, P and Q are predicate variables and D is the domain for x. Why is the logic sentence in the image considered to be a statement (or proposition)? A statement is a declarative sentence that is either true or false but not both. But for the logic sentence above, we can't decide if it's true or false until we're given some values, like what sentence P and Q represent.

[vital locust]

Prove that a tree $T = (V,E)$ with $|V| \geq 2$ has exactly two leaf vertices if and only if it is a path.

[vital dew]

Certified Thot Slayer

[vital locust]

I am trying to prove the first direction

by using induction on |V|

but i am stuck on the inductive step

[agile magnet]

what is the definition of a tree that you are working with?

@vital locust

[vital locust]

it has exactly two leaf vertices

[brittle glacier]

Hello guys i wanna ask something, do you guys have any book recommendation for cryptography ? I'm currently finishing kenneth rosen's discrete math book, what should I read after that to study in depth about cryptography ? Thanks

[vale cairn]

I eould just say this is a poor example

[agile magnet]

I meant like in general. There’s some definition you’ve been told. I want you to tell it to me

If you don’t know the definition of a tree, then how can you prove something about a tree?

[regal ice]

Is this the correct generating function for the partition of 7?

[toxic hollow]

hello can anyone help me with thisThere are four candidates to choose from for an election. 302 people are there to vote. What is the minimum number of votes needed for someone to win the election? for this question if we divide 302/4=75.5 means 76 according to pigeonhole but in this case 2 candidates get 76 votes so in this case the ans will be 76+1=77 ?

[vital locust]

A tree is a connected graph with no cycles

[agile magnet]

I don't see how you can induct on |V|

You're told |V| ≤ 2

Hang on that makes no sense

Did you type that correctly?

[vital locust]

sorry it should be greater than of equal to 2

not less than

[agile magnet]

I don’t think you need induction

Maybe try that direction by contrapositive

[vital locust]

So smthn like suppose T is not a path then the degree of all it's vertices are greater than or equal to 2

then i think there's a theorem that says the degree of every vertex is greater than or equal to two

you have a cycle

a contradiction since T is a tree and must be acyclic

so T must be a path?

[agile magnet]

Not all of it’s vertices but essentially yes

You have two leaves but if it’s not a path there’s some node of degree > 2, argue there. Just be a cycle

That’s how I’d do it, some details to iron out

[vital locust]

if there is at least one node of deg > 2 how can i argue there is a cycle

i'm confused on that part

[agile magnet]

Two cases, it has two leaf nodes or it doesn’t

Hmmm maybe this doesn’t work lemme think more

Ok let’s try from the beginning, it should work

But cycles aren’t the key

Ok so suppose T is a tree

And suppose it has two leaf nodes, but isn’t a path.

There must be a node of degree > 2

Can you derive a contradiction?

It’s a tree, so no cycles still

[vital locust]

drawing up some examples

like the a tree on 4 vertices with exactly two leaves

if we assumed it wasnt a path

they're already 2 nodes with degree >= 2

[vital locust]

so i'm still confused on how to get the contradiction from this result

[agile magnet]

Can you argue there must be a 3rd leaf stemming from that node of degree > 2

Hence contradicting the fact we have only two leaves

[vital locust]

i'll give it a try

i'm still abit confused on how to argue this way i think i'll go review the trees section and try this again

thanks for the all the help

appreciate it

[tawny holly]

I got this question in my mid, and i dont fully understand part 1

""because y is in S and y is in T, we have x in f(S) and f(T)"" specifically this

[agile magnet]

what is y?

y is an element in S, and y is an element of T yes?

[tawny holly]

Im guessing the input for function f

[agile magnet]

yea

[tawny holly]

Why S and T?

[agile magnet]

it's an element of A

[tawny holly]

Oh element

[agile magnet]

what is f(S cap T)

[tawny holly]

Ye ok

[agile magnet]

$f(S \cap T)$ what is this set?

[vital dew]

Spamakin🎷

[agile magnet]

can you give me the definition?

[tawny holly]

An input for f that is an element in both S and T

And f is a mapping from A to B

[agile magnet]

no

almost though

it's the set of outputs of f if you apply them to elements in S and T

$f(S \cap T) = { f(y) \mid y \in S \cap T}$

[vital dew]

Spamakin🎷

[agile magnet]

so if x is in f(S and T) then x = f(y) for some y in S and T.

that's how they got that part of the proof

that make sense?

[tawny holly]

Yup that helps

Ty

[agile magnet]

so then from there

So since y is in S, then f(x) must be in f(S) right?

[tawny holly]

True

The same goes for T too

[agile magnet]

bingo

[tawny holly]

Got it

[agile magnet]

so x in f(S) and f(T)

[tawny holly]

One more q

This was another one of the questions

No one got it right

Makes absolutly no sense bo me idk where I should even start

[agile magnet]

which part?

[tawny holly]

I gotta make sets that fit the definition but the definition doesn't make sense

Pretty sure the prof made it up

[agile magnet]

they probably did, doesn't matter

ok so it's a collection of universal sets such that if you intersect k of them, it's nonempty

but if you intersect k + 1 of them, it's empty

[tawny holly]

What abt subsets j

[agile magnet]

?

J is just a subset of indices in I

[tawny holly]

What does that mean

[agile magnet]

so I is just some set of indices, say the natural numbers

so every natural number is some index

and we're using these to label some collection of subsets

[vital dew]

Spamakin🎷

[vapid lion]

Hi

[vital dew]

Spamakin🎷

[agile magnet]

that clear things up?

[tawny holly]

so if the number of sets is odd then the intersection is not empty if its even its empty?

[agile magnet]

no

[vital dew]

Spamakin🎷

Spamakin🎷

Spamakin🎷

[tawny holly]

still having trouble understanding

[tawny holly]

can u go over one of these examples

k = 2 n = 3

[agile magnet]

yea so if I intersect any of the 2 sets in that solution

it's nonempty right?

k = 2

[tawny holly]

true

[agile magnet]

but if I intersect k + 1 = 3 of them, it's empty

so there's a collection of 2-fabulous sets

[tawny holly]

then why is this not right?

[agile magnet]

where are you getting odd or even?

none of this has to do with k being odd or even?

[tawny holly]

ur right, the k + 1 mixed me up

its not 2k so that doesn't work

[tawny holly]

ok but if we start at k = 3. then its not empty. then k + 1 = 4 would be empty?

[agile magnet]

if you had a collection of 3-fabulous sets, then yes

[tawny holly]

here, what would be an example of k + 1 = 3

part 3

[agile magnet]

well

there are only 3 sets

take their intersection

it's empty

[tawny holly]

OH

so the intersection of all 3

instead of any 2

I think I get it now

Ty

[glossy willow]

is x+1=2 a proposition

[sour python]

hey

if u had a power set = {{},{9}}

times another power set {{},{8}}

is the ordered pair {({},{}),({},{8}),

so on

{({},{}),({},{8}),({9},{}),({9},{8})}

[agile magnet]

Yes

[worthy shale]

Does relation and function comes under #discrete-math ?

[coral parcel]

Yes, or alternatively #proofs-and-logic.

[vale shell]

What do you guys think about theorem 2 in this Graph theory video? https://youtu.be/Rbs1wmNGwr8

I think its an idea for induction?

[coral parcel]

Nothing. Can you state the theorem so we don't need to spend our time slogging through a video just to find out what you're talking about?

[vale shell]

Explanation/animation of the theorem is in the video.

[vale shell]

If you dont want to see then no need to comment like that.

[worldly slate]

does anyone know a good video that can explain loop invariants?

[chilly dew]

I checked using a script but is there any way to analytically show that T(n) < R(n) for n > 520 given the fact that it is true for n in the range [521, 1 million] ?

T(n) = 7T(n/2) + 18(n/2)^2, with T(0) = 1 and T(2k - 1) = T(k) for k > 1

and

R(n) = 2n^3 - n^2

[chilly dew]

I feel like the fact that T(n) < R(n) for two consecutive powers of 2 (n = 2^k, 2^{k+1}) should be enough to prove it, but I'm not quite there

[elder berry]

I don't think this is what you are searching for, but using the Master theorem, T(n) is Big Theta of n^(log_2 (7)) while R(n) is Big Theta of n^3 so in the limiting case T(n) < R(n).

[chilly dew]

Right yeah, I'm just trying to explicitly find the "sufficiently large value n_0" such that T(n) < R(n) for all n > n_0

and empirically it appears that n_0 = 520

but showing it rigorously is a bit challenging for me, even with the information that it holds for 520 < n_0 < 1 million

[vale shell]

Fake username, fake photo, only brave in the internet

[true venture]

How could you find all the numbers that can be partitioned into square parts with a symmetric Ferrers graph?

This includes but is not limited to numbers of the form,
2a+1
a^2
a^2 + 2(b-a)
Where a and b are squares and b>a. There are other forms included but these are the smaller ones.
The numbers below 100 I beleive are, {1,7,16,17,26,31,40,49,58,71,80,81,95,97} trying to think how I could write a program to find more?

[vestal bronze]

you mean all forms are known?

[small plume]

am I tripping or is this not true?

[vestal bronze]

empty set is always a subset

of anything

[small plume]

if the power set of {1, {1,2}} is { ∅, {1}, {1, 2}, { 1, {1, 2}} so intersection of {∅} and { ∅, {1}, {1, 2}, { 1, {1, 2}} is ∅ right ?

ohh

I thought the intersection was {∅} at first

[vestal bronze]

and also is an elment of any powerset

[small plume]

so I was like how could ∅ be a subset of {∅}

[vestal bronze]

so ∅ ... P is true whichever symbol is skipped

[small plume]

there is no intersection between these two sets though, right --> {∅} and { ∅, {1}, {1, 2}, { 1, {1, 2}}

so it ends up just being ∅

just want to make sure my reasoning is correct

and ∅ is obviously a subset of itself

[vestal bronze]

no the intersection is {∅}

must be tripping then

[small plume]

how though ?

one is a set containing the empty set

and one contains just the empty set

[vestal bronze]

yeah

[small plume]

where's the intersection

[vestal bronze]

so 1 element in common

[small plume]

a set containing the empty set and the empty set are synonymous ?

I thought they weren't the same thing

[vestal bronze]

no

[small plume]

wtf

so how is there an intersection

[coral parcel]

Because there is something that is an element of both of them

Namely Ø.

[vestal bronze]

the intersection is a list of common elements

∅ is an element

[small plume]

so it doesn't matter if one is in a set or not

just matters if it's contained in the set

I see

[coral parcel]

"Contained" is an ambiguous word.

[small plume]

what word would be more suitable

an element of the set?

[coral parcel]

Either "element of" or "subset of", depending on which of the you mean.

[small plume]

hmm

[vestal bronze]

there's no intersection between {∅} and {1,2}

[coral parcel]

(Which is a conventional but slightly confusing way to say that the intersection is the empty set).

[red dust]

but an empty set is a subset of everything, that's one of the axioms afaik

[coral parcel]

It's not an axiom as much as it's a direct consequence of the definitions of "empty set" and "subset".

[true venture]

No, the forms I listed are just the ones with values under 100.

[weary tiger]

Edit: Nvm found it!

[viral haven]

Is there an efficient algorithm to find the number of solutions to

x_1 + x_2 + ... + x_n = c

Where c is known and for all x_i in the range [1, p]? And all variables involved are positive integers

[true venture]

So partitions of c with parts <= to p?

[coral parcel]

Is n given, or do you want to count solutions with different n?

[viral haven]

More like compositions but yes

[viral haven]

Yes sorry n is given

[coral parcel]

Darn, that makes it harder.

[viral haven]

I'm trying to make a recursion for it but it's hard to reason

[agile magnet]

Isn't this stars and bars

[coral parcel]

You could use dynamic programming in time O(pnc), but that probably won't count as efficient.

No, it's not stars-and-bars because there's a limit on the size of each x_i.

[agile magnet]

Oh wait p is a thing

Ok yea dynamic programming is my instinct

O(nc) ain't bad, technically you could bound it by O(n^2 p) since your max sum is np

That's getting into semantics though, maybe p large c small

[agile magnet]

What decisions can you make?

That's the start of every recursive definition

There's some choice you can make, or choices, let's find them and see if they give us useful sub problems

[unreal stump]

Wouldn't this just be coefficient of $x^c$ in $\left(\frac{x(1-x^p)}{1-x}\right)^n$?

[viral haven]

My actual problem is p = 4, 0 <= c <= 64 and 1 <= n <= 16

So as long as its pretty quick it's all good

[vital dew]

DraK

[unreal stump]

You can like get the form from this by hand

[viral haven]

Or find derivatives and evaluate at 0

If what you say is true that's got potential to be fast thank you

[unreal stump]

Well yea you know expansions of (1-x)^-n

You know expansion of (1-x^p)^n

[coral parcel]

Yeah, there I would just do the dynamic programming solution. Trying to be more clever than that wouldn't pay off in terms of time.

[viral haven]

I always forget to use the exponents of polynomials in problems like this

Such an obvious start too

[viral haven]

I appreciate that but a taylor series of this could be useful. Allows me to analyse it for the larger problem im trying to solve. Thank you for your insight

[unreal stump]

nvm there you go

So the whole thing boils down to how fast you can compute binomial coefficients

You can probably hack and make it faster

[viral haven]

How did you get this? I'm thinking the coefficient of x^c in (1 + x + x^2 + ... + x^p)^n gives the same result. Are these equivalent?

[unreal stump]

Yea

Same thing

Well it should start with x

Because positive

[viral haven]

Oh sorry I'm solving the larger problem

Which allows there to be 0s

But yes agreed for the problem I proposed

[unreal stump]

Ah nvm that's correct then

[viral haven]

Thank you ❤

[analog hound]

Why does assuming G is maximally non-Hamiltonian not lose generality? What if the theorem is not true in general for graphs that satisfy the condition on the minimum degree but are very non-Hamiltonian?

[coral parcel]

For it to make sense, I think we have to consider just a single n, and look at maximal non-Hamiltonian graph among graphs with that many vertices.

If you're looking at a non-Hamiltonian graph with delta(G) >= n/2 that is not maximal, you can always keep adding edges to it until there's no way to add another edge without introducing a Hamiltonian. At that point it is, by definition, maximally non-Hamiltonian, and adding edges cannot have made delta(G) >= n/2 stop holding.

[analog hound]

Right, but I thought the contradiction supposes there exists some kind of non-Hamilton graph with n vertices and delta(G)>=n/2 (so not necessarily maximally non-Hamiltonian). I don't see why we maintain generality just because the bound on delta was not broken

Is there some way in which "Hamiltonicity" does not depend on what edges you have to the extent that the bound still holds...?

[coral parcel]

No, you simply avoid adding any edge that would cause the graph to have a Hamiltonian cycle.

The "without loss of generaility" is the implicit argument "if there exists some kind of counterexample, then there also exists a counterexample that is maximal among all counterexamples".

[analog hound]

Right, but the converse is not necessarily true no?

I thought the argument supposes it is

[coral parcel]

The converse is, um trivial.

[analog hound]

Oh let me think a second

Ah yes

[coral parcel]

Instead of addinge edges we could also think in this way:
Consider the set of all graphs on n vertices that have delta > n/2 and are not Hamiltonian.
We are assuming this set is not empty.
Since it is not empty, one of the graphs in it must have the largest number of edges that it is possible in for any graph in the set to have.
(Because there cannot be more than n choose 2 edges anyway).
This graph with the largest number of edges must be such that if we add any edge to it, the result is Hamiltonian.

[analog hound]

I think I see: if there is not a maximal counterexample, and the set of counterexamples must either be empty or contain a maximal element, the set of counterexamples is empty

That makes sense, thanks for the help!

[chilly dew]

Let X be a set, and define xor_{x \in X} x as ((...((x_1 xor x_2) xor x_3)...) xor x_n) where X = {x_1, ..., x_n}. If X = {x} is it safe to assume that the quantity will just be equal to x

Like obviously the notation should be more clear but if you all had to guess

[unreal stump]

Yes?

[coral parcel]

Don't ping random people for help.

That makes most people less likely to want to help you.

The blue diamond means he has declared he is a he/him.

[lucid charm]

could i get some help

[coral parcel]

If you ask a question, perhaps someone who reads it will feel qualified to answer it.

[lucid charm]

Let U = {apple, banana}. Define the relation R ⊆ 2^U x 2^U as follows:
ARB if and only if A ⊆ B.

im trying to show that this is a partial order

and i know partial order is ref, transitive and antisym

but i dont know how to show these from the relation

iguess i just dont know what im trying to do with the relation

[coral parcel]

Which of them do you have trouble checking? Take them one at a time.

[lucid charm]

its not that i dont know how to check the partial order

[lucid charm]

i dont know what to do with this part

[coral parcel]

That tells you which relation you're being asked to check.

You can, if you want, write down the four elements of 2^U explicitly, which may help you visualize what's going on.

There are sixteen pairs in the cartesian product 2^U × 2^U; nine of those turn out to be in the set R the problem defines. You can work out those explicitly too.

[lucid charm]

ok so i wrote that:
reflexive: since A is subset of A, we know that this shows equality and therefore reflexive
transitive: since A subset B and B subset C, we know that all values of A are in C, therefore A subset C and transitive
antisym: Since A subset B and B subset A, then A must equal B from def of subset

but this isnt a good proof at all

or at least it doesnt feel concrete

[coral parcel]

I'd say that is an excellent proof. Full marks if I were grading.

[lucid charm]

oh really? ok then i guess its good!

how would i draw a hasse diagram for this

[coral parcel]

Then you do need to write down the elements of 2^U explicitly -- but there are only 4 of them, and they turn out to arrange in a nice diamond-shaped Hasse diagram.

[lucid charm]

could you explain how to draw hasse diagrams? we didnt do much on it in class

the only example the prof gave was getting dressed in the morning LOL

[coral parcel]

There's not much of a procedure. For examples as small as this you just wing it.

[lucid charm]

but how do i start it

i literally have no clue what to do for it

[coral parcel]

If you google for Hasse diagram of power set you'll discover that the relevant Wikipedia article starts with exactly the diagram you need. :-)

[lucid charm]

ok dope thanks

[chilly dew]

hey tropo

are you familiar with karatsubas algo

[coral parcel]

No.

[chilly dew]

it allows you to compute the three quantities ac, ad + bc, bd in only three multiplications (as opposed to four) by computing ad, bc, and (a + b)(c + d) - (ad + bc) = ad + bc

there should be a similar thing for computing the five quantities ad, ae + bd, af + cd + be, bf + ce, cf in only six multiplications (as opposed to nine), but I can only get it down to seven

the method for seven being:
compute ad, ae + bd, bf + ce, cf, and (a + b + c)(d + e + f) - (ad + ae + bd + bf + ce + cf) = af + cd + be

but that's one too many multiplications

[unreal stump]

Well yea you substitute a multiplication with a couple of additions

[chilly dew]

is that a hint

[unreal stump]

Well that's like ultimately what you do

[coral parcel]

You can get ae+bd and bf+ce with the original Karatsuba trick. You're already computing ad and cf, and the two computations can share a single computation of be.

But the whole thing will not really be an asymptotic improvement anyway, because log_3(6) > log_2(3).

[chilly dew]

(a + b)(d + e) = (ae + bd) + (ad + be)
(b + c)(e + f) = (bf + ce) + (be + cf)

Compute ad, be, cf. Then (a + b)(d + e) = (ae + bd) + (ad + ce) and (b + c)(e + f) = (bf + ce) + (be + cf). We still need to compute af + cd + be right

well we already have be but still need af and cd

[coral parcel]

You can do that with what you already have above, or compute af+cd as (a+c)(f+d) - cf - ad.

[chilly dew]

I understand the second part of that (hooray)

but wdym by "You can do that with what you already have above"

[coral parcel]

The final part of this.

[chilly dew]

hmm I'm confused

[chilly dew]

here I just said to perform the five multiplications ad, be, cf, (a + b)(d + e), and (b + c)(e + f)

and then asked how to find af + cd + be in one multiplication

[coral parcel]

But that's what you already gave a recipe for: (a + b + c)(d + e + f) - (ad + ae + bd + bf + ce + cf) = af + cd + be

[chilly dew]

ohhh you were replying to that message

ok yeah I see what you're saying

thanks

apparently it can be done in 5 multiplications btw (but it's much harder to come up by toying around)

and the generalization is https://en.wikipedia.org/wiki/Toom–Cook_multiplication

[lucid charm]

i need some help with reflexive transitive and symmetric

[outer kayak]

how do i approach this?

[chilly dew]

find out

1. in how many different ways can we see three heads and three tails (e.g. HTHTHT and HHHTTT are two examples)?
2. what is the probability that a particular occurrence in 1. occurs (hint: they're all the same)?

[outer kayak]

the second option?

[chilly dew]

I'm asking you to find the probability that the sequences of tosses comes out HTHTHT, and the same quantity for every other sequence you find in 1.

[outer kayak]

i see alright

[shy basin]

guys i have a question

X = {∅} => X = ∅ this is false right?

[torn tendon]

yes

[shy basin]

nice thx

[wise garnet]

guys how do you learn discrete math

[plush canyon]

how does it become n/n+1 ?

oh shit nvm i see

[agile magnet]

That's the claim, you see it becomes that in the proof

[grave moon]

Is x^3=0 one to one function?

[stray reef]

this isn't a function at all.

[grave moon]

No. It's a function.

You are confusing me.

[jolly ledge]

[stray reef]

??

[jolly ledge]

Do you know the definition of a function

[agile magnet]

if it's a function can you tell me the domain, codomain, and how elements are mapped from the domain to the codomain?

[analog tinsel]

read , think , exercise in short. Studying the math from a book, then really trying to understand everything until I could explain it to someone else and then doing a lot of exercises

[grave moon]

f(x) = x^3
domain & co domain Real number.
is it bijective?

[ivory badge]

Well, is it one-to-one (injective) and is it surjective?

[agile magnet]

f(x) = x^3 and 0 = x^3 are different things. But yes f(x) = x^3 with the domain and codomain of the real numbers is a function. 0 = x^3 is not

[grave nexus]

Yes , it's bijective , as it is both injective and surjective.

[grave nexus]

For subjectivity , f:ℝ->ℝ defined by f(x) = x³ or y = x³
∀ y ∈ ℝ (co domain) ∃ x ∈ ℝ (domain)
∋ f(x) = f(³√x) =(³√x)³ = x³ = y
Therefore , f(x) = x³ is surjective.

[marble kindle]

find all solutions of this recurrence relation an=4(an-1)-3(an-2)+n+3 with initial conditions a0=1 and a1=4

can anyone please help me with this

[marble kindle]

I found first 6 terms,1,4,18,66,217,678,2070

But I can’t seem to find a formula

[low flicker]

you can solve the recurrence relation to find the general solution

separate the relation in linear homogeneous and the polynomial part

[low flicker]

can someone provide me an example of proving the sequence like sum of squares, sum of cubes using strong induction? i cant see any example

like for this question i can do it with mathematical induction

how to implement the hypothesis p(j) is true for 0<= j < k for k>0 in a proof .?

so i guess the only thing which differs is induction hypothesis? or somthing else required in further implementation ? i am completely lost

[ionic tulip]

Lets say I have an expression, and the question asks us to prove that that expression is divisible by some integer for some natural number n, and we can't use induction. Is there some general way to do it? Like looking at remainders for example

[chrome osprey]

yes its true

its just the induction hypothesis

and if n > the first possible value in a recursive function

u need to individually hand prove the base cases

for example, b_n = b(n-1) + b(n-2) + b(n-3)

and then bn = 5n

or smth

u cant find case 1 2 3 using the recursive function, because they dont have enough prior values

[low flicker]

yes i was thinking same

so for above problem. i'll do for the p(k) first and copy everything in the next proof assuming p(j) is true for 0< j < k for k>0
And rest is same as the previous ordinary induction

[agile magnet]

Remainders is a common approach yea

Anything more specific I can't think of off the top of my head

I'd have to see the question probably

[real aurora]

What is the probability of an infinite random walk on a finite bidirectional fully connected graph reaching any particular vertice?

[jolly ledge]

Ehhhh I was thinking number of elements in A would not be equal to B? Since A would be (some number) choose 3 and B would be (some number) choose 4... unless the number of people are 7, this won't be true would it

[vale cairn]

There are 7 people ig from what they say

[jolly ledge]

Ah

Lmao... ngl tho it seems a bit misleading since they made it sound like a general case ("we'll name the members of the people 1 to 7 for simplicity, but this works for the general case")

[vale cairn]

Oh yeah sure

I guess this is just saying n choose k is n choose n-k

Which book is this, knuth?

[jolly ledge]

Nah not rlly, just some book I picked up cuz I was beginning to feel burnt out with maths. Basically meant to cover mathematics without going into computation and arithmetic. That being said, sometimes the fact that it's not 100% accurate irritates me XD. It's called "the mathematics lover's companion", apparently its by Yale uni press ignore the irony in reading a maths book despite being burnt out by maths

[wild field]

hey guys, good evening/afternoon/morning

how can I study discrete maths?

and how can I apply it in computer science?

[jolly ledge]

By reading a book on it and doing the exercises.

Common recommendation is Rosen

I had a look at it and am currently reading it, it's not bad at all

[junior oak]

anyone here know predicate math

[lyric quartz]

Sure

[shy basin]

why is the relation {(1,3),(3,4),(1,4)} for {1,2,3,4} not transitive?

[agile magnet]

?

It is transitive

[shy basin]

not according to this

@agile magnet

[agile magnet]

That calculator is wrong as far as I can tell

Think about the definition of transitive

Super easy to check here

And no counter examples

You cannot find elements a, b, c such that (a, b) and (b, c) are in the relation but (a, c) is not

[shy basin]

yeah i think ur right

https://relcalculator.freevar.com/ this is the calculator if u want to check it out

[fresh laurel]

Find a topological sort T of each of the following graphs:
G = [A :Z; B : T ; C :B; D : Ø ; X : D; Y : X; Z :B, X; S :C, Z; T : Ø ] help me i dont know how to its direted graphs

[lyric quartz]

Wow it uses two different notations for a set, with just two inputs 😛

[upper trout]

does anyone know how to do the rest of this proof

I’m stuck on what to do next😭

[inner otter]

maybe try distributivity on the RHS?

I can't tell if that's what you've done already

[upper trout]

thats what im trying but my brain has ceased to function

im up to the point on the bottom left where im trying to do more with the inequality

[inner otter]

no I meant instead of just writing it as $\frac{3}{4} (k + 1)^{3/2}$

[vital dew]

cwatson

[upper trout]

sorry im still a bit unclear of what you mean by this

oh wait I think I get you, I already did that but its just a little messy, i added an arrow pointing to what (k+1)(sqrt{k+1}) can be

The bottom part is the most recent and I have been trying to get the RHS to work out to 3/4(k+1)^3/2

[inner otter]

I meant writing $\frac{3}{4}(k + 1) \sqrt{k + 1} = \frac{3}{4}k \sqrt{k + 1} + \frac{3}{4} \sqrt{k + 1}$

[vital dew]

cwatson

[inner otter]

Does that help things along?

[upper trout]

yes it does, thank you!!

[tidal anvil]

whats the inverse of a floor function :(

[unreal stump]

Doesn't exist

[tidal anvil]

big rip

[jolly ledge]

[regal gate]

Given $a,b\in \Z$ is it possible to count, for every $n\in \mathbb N$ the number of functions $f\c {1,\dots,n}\to {-1,+1}$ such that $b<\sum_{i=1}^N f(i)<a$ for every $1\leq N<n$ and $\sum_{i=1}^n f(i)=a$?

[vital dew]

Croqueta

[fast citrus]

@shy basin helpers

[marble kindle]

Can someone help me with this?My question is basically the numbers losted there 1 3 5 are all odd,should i still take 2k+1 as inductive step and k as base step?

[torn tendon]

no , because you want to prove this for all $n$ , even if the numbers are odd , what you are proving is that $$\sum_{i=0}^{n}(2n+1)^{2}=\frac{(n+1)(2n+1)(2n+3)}{3}$$ so if you pick $n=2$ , then what we get on the left side is $(2(0)+1)^{2}+(2(1)+1)^{2}+(2(2)+1)^{2}=1+3^{2}+5^{2}$ despite picking $n$ to be even.

[vital dew]

Susilian

[marble kindle]

Got it thanks so much 🙏🙏

[torn tendon]

i should have said 2i+1 in the sum but you get the idea

[silver portal]

Hello, can somebody help me please with this question?

how many subgraphs isomorphic to c4 are there in km,n

[agile magnet]

@silver portal ok so

[vital dew]

Spamakin🎷

[silver portal]

There are 3 subgraphs isomorphic to C_4

[agile magnet]

yea

so how did you come up with that

lets see if we can take what you did and generalize it to K_m, n

[silver portal]

Less vertices = less work

It is easy to decide when there are not many vertices

[agile magnet]

well sure you could have brute forced this, it is a small example

do you want to try a larger example? Say K_4, 3?

[silver portal]

Exactly

Ok let's try

[agile magnet]

hopefully this is too large an example to brute force

so try to think about what choices you have to make

choice that uniquely determine the 4-cycle

[silver portal]

I found 6 of them

[agile magnet]

there should be more

[silver portal]

Alright hmm

[agile magnet]

try to think about this

this is how you do counting problems: thinking about choices

[silver portal]

I counted them 8 this time

[agile magnet]

no

again, think about what I wrote. What choices do you make?

[silver portal]

So, firstly we know that our graph must be atleast of K_2,2

Right

[agile magnet]

wdym by that

[silver portal]

There is only one subgraph

[agile magnet]

there are more subgraphs than K_2, 2 of K_m, n

for example C_4

[silver portal]

Right

I mean

I have to find out how many of C_4 are in K_m,n

[agile magnet]

wait no I'm dumb K_2, 2, = C_4

ok uh K_2 is another subgraph of K_m, n

[silver portal]

So our variables m,n have to be atleast 2

[agile magnet]

anyways not the point

yea

ok so m, n >= 2

[silver portal]

Yea

[agile magnet]

that doesn't really answer my question about what choices do we have to make when finding a copy of C_4

[silver portal]

I'm not sure what do u mean by "choices"

[agile magnet]

how did you enumerate the 3 graphs here

[silver portal]

In the photo?

[agile magnet]

yea

[silver portal]

It must contain 4 edges

And we need circle graph

So we must start and end in the same vertex

[agile magnet]

ok so I like the "must contain 4 edges" and so by extension it must contain vertices

and also we start and end at the same vertex

so one choice we make is our start vertex

right?

[silver portal]

Sure

[agile magnet]

then what is another choice?

say in your picture

we choose one of the v_i to start at

what next

[silver portal]

And V_i+1 to continue

Is second choice

[agile magnet]

why v_i+1?

where did the +1 from from?

[silver portal]

I mean second vertex

I cannot go back to the same one

[agile magnet]

cause one of your graphs has v_1 and v_3 but 3 != 1 + 1

ok right right

so we pick two of the v_i

out of the m vertices right?

[silver portal]

Right

[agile magnet]

what about the other two vertices? how can we pick those

[silver portal]

and also two from n

[agile magnet]

right

and order doesn't matter right?

[silver portal]

Not at all

[agile magnet]

picking v_1 first and then v_3 is no different than choosing v_3 then v_1

cause it's an undirected cycle

[silver portal]

I see

[agile magnet]

do you see why picking two of the m vertices

and two of the n vertices

uniquely determines a copy of C_4?

[silver portal]

I suppose

[agile magnet]

try it out yourself

on K_3, 2

enumerate the choices for the m vertices, and the n vertices

and you'll see you arrive at 3 again

[silver portal]

Alright

Let me see

So I have 3 choices for m vertices however only one choice for n vertices

Correct?

[agile magnet]

yup

so 3 * 1 = 3

get our 3 subgraphs that you drew out

[silver portal]

Let me try your second example

For K_4,3

I have 5 choices for m vertices and 3 for n vertices, then there should be 5*3 subgraphs

[agile magnet]

how did you get 5

do you know the formula for "I have n objects, I want to choose k of them where order doesn't matter?"

[silver portal]

So I'm picking from an unordered set

[agile magnet]

yea I have n objects

and want to pick k of them

so here we have 4 objects, and I want to pick 2 of em

there's a formula you should know for this

[silver portal]

So isn't it the combinatoric number?

[agile magnet]

I've never heard that term before

can you write out what you mean?

I think we're talking about the same thing but I want to make sure

[silver portal]

Its basically n over k

[agile magnet]

???

no it's not n / k

[vital dew]

Spamakin🎷

[silver portal]

Yea

[agile magnet]

what's the formula for this?

do you know?

[silver portal]

With the factorials?

[agile magnet]

that's the one

write it out for me, and then compute 4 choose 2 for me

you shouldn't get 5

[agile magnet]

perfect

ok so in general

[vital dew]

Spamakin🎷

[agile magnet]

give me a general formula

[silver portal]

Let me think

Hmm

Not exactly sure

So I need to use the binomial two times

To calculate m and n

And then multiply them

[agile magnet]

yup

so what is your formula

[silver portal]

I mean in our case we could replace the variable k for 2

And yeaaa, we can even reduce it further

So this should be our final general formula

[agile magnet]

sorry for leaving lol but yes

and really I'd write it like this

$\binom{m}{2} \cdot \binom{n}{2}$

[vital dew]

Spamakin🎷

[agile magnet]

to really emphasize that you're making these choices

[silver portal]

Great! Thanks a lot... Really appreciate it

[echo night]

Just a general wondering

How can something have a inverse modulo

Because to be like

24^-1 mod (7)

Don’t u need to be 7 1/24?

[obtuse lance]

it's something you multiply that number to get remainder 1

so 24^-1 is a number that when multiplied by 24 has remainder 1 when divided by 7

5 is one choice

you can work that out, multiply 5*24 and then see what remainder you get when you divide by 7

[flint pawn]

(reposting here since I realized this might be too much for the general help channels)
I know that for a normal undirected graph the density formula is D= 2|E| / |V|(|V|−1), but this is multiple disconnected graphs. Can calculate the densities individually and sum them?https://cdn.discordapp.com/attachments/490557019623915520/1095987973633351781/image.png

[obtuse lance]

you can calculate |E| and |V| independently

try working out a few examples by hand see if you can spot the pattern

what are |E| and |V| for n=2 or n=3?

[flint pawn]

For n=3 wouldn't it just be 3 and 3?

[obtuse lance]

nope, that's n=1

oh you're right sorry I'm wrong

I was thinking n was the number of triangles

I meant to ask n=6 and n=9

[flint pawn]

Am I overthinking? Is it just 6 and 6 for n = 6 and 9 and 9 for n = 9?

[obtuse lance]

yeah that's all it is

[flint pawn]

Oh LOL

[flint pawn]

Just to be 100% clear, since E and V = n can I just plug n into the formula?

[obtuse lance]

yup

show what you get if you want me to check

[flint pawn]

Density(n) = 2/(n-1)
If n = 12, d = 2/11

[true venture]

If I were to count compositions of n, such that the differences between neighboring parts equals the number of parts, should n itself be counted?
Ex. For n = 4
Would that include (4),(13) or just (13)?

[marble kindle]

Hey guys, can some give me tips for finding formulas for sequences? There are some really tough one like for example there was one that went like 1,2,1,2,1,2 which basically was n%2+1 or smth like that

And another was which was floor function of n/2

Any way to deal with these tough ones except for just logically guessing?

[true venture]

Try looking at the differences of the terms.

[marble kindle]

But that won’t help everytime tho

[true venture]

It will at least tell you something about the sequence, then you can look at the differences of the differences.

[neon summit]

U= 2x + y^3 -3x^2y find anaylatic function by Milne thomsan , method please tell me that answer is( 2z + i z^3 + c) or( 2z - i z^3+ C )

[vivid gust]

does anyone understand first order linear recurrences?

i need help understanding it

[zinc kettle]

whats the proper name for a polynomial that counts amount of ways a positive whole number can be represented as a sum of lesser positive whole numbers in english (the original number alone also counts as a representation). in my college professors call it "enumerators" but i havent found any info about it on wikipedia or google, it seems as if my college literally made it up

[vale cairn]

Hm shouldn't be a polynomial

[vivid gust]

does anyone understand first order linear recurrences?

[zinc kettle]

its a product of polynomials that can be also written as a product of geometric sequence sums, I will send an example in a sec

[vale cairn]

But p(n) is the partition function if that's what you mean

[vale cairn]

Ah yes

[zinc kettle]

oh yes thanks

[vivid gust]

i’m still confused

could i dm you separately and you can walk me through a problem

[zinc kettle]

sry idk anything about first order linear reccurences

[vivid gust]

oh ok

[glossy willow]

just ask the question here

its unnecessary to keep asking if people know what you want

just ask the actual question you need help on and if someone knows they will guide you through it

from a quick google search it just looks like a geometric series for a simple reccurence of x_n = r*x_(n-1)

[grand marten]

a little more on the compsci side of things but, is there a way to generate a list of products a * b with a and b less than n (n is an arbitrary number of our choosing) such that the resulting list of products is sorted in descending order?

[tight hound]

Yes, there exists a way.

[tight hound]

I don't get the purpose behind your question though. Were you looking for a solution within specified complexity bounds?

[agile magnet]

Is there anything better than just compute products and sort?

Probably tbh but sounds annoying

[agile magnet]

If each list has n elements then this runs in n^2 log n time

Maybe there's something funky with convolutions but probably not

[pliant gull]

ln(1+x^6) how can ı find maclaurin serie of it?

isnt there anyone to help me??

[worthy pivot]

there is, in another channel

[lyric quartz]

It's the Taylor series at x = 0

[magic knoll]

oh wait nvm

[deft sage]

Homotopy type theory is a descretizatiom of continuous objects

you don't have continuous surfaces.
You turn paths into a single deacrete object.

a descrete interpretation of a path is as am equality between 2 objects

[lyric quartz]

#foundations ?

[deft sage]

i dont have permissions for that

[drowsy helm]

Any suggestions on how to go about proving that all Steiner Triple Systems of order 7 are isomorphic to the Fano Plane?

Or might this be a better question for #combinatorial-structures

[weary tiger]

can someone help me understand proofing by contradiction?

[shy basin]

its like assuming something that you know is wrong, and carrying the logic until you get to a false statement(s)

[inner otter]

not quite

[shy basin]

[weary tiger]

so what is the difference between proving by contraposition and proving by contradiction?

[inner otter]

I guess I'm just being pedantic, RE the phrase "something that you know is wrong"

[shy basin]

i guess you could assume something that is true

it really depends on the context

[weary tiger]

Proof by contradiction that at least 4 days of 22 chosen days fall on the same day of the week

like this

i just can't understand the answer

[shy basin]

assume tht you can choose 22 days such that less than 4 of them fall on the same day of the week

?

[inner otter]

Think of the "classic" proof that the square root of 2 is irrational. For proof by contradiction, you assume square root of 2 is rational, and reach a contradiction or an absurd conclusion

[shy basin]

try to do this

if its impossible

proven by contradiction

[weary tiger]

Any 22 days?

[shy basin]

ye

and yes its impossible

3 weeks is 21 days

the last day will have to fall on one

making that day of the week have 4 of the 22

[drowsy helm]

That’s classic pigeonhole principle too

[ivory badge]

Contrapositive is that (P->Q) is equivalent to (Not Q -> Not P)

Contradiction is assuming A is false, and deriving a contradiction so that Not A is false

So it uses Not Not A -> A

[ivory badge]

This isn’t quite contradiction as this assumes P and gets a contradiction so you derive -P

[inner otter]

Yes I suppose that's right.

My understanding of proof by contradiction is that if you want to prove (P -> Q) you assume (P ^ -Q) to reach a contradiction

[jolly ledge]

[weary tiger]

What would be the best channel to ask questions related to graph theory. I'm interested specifically in the problem of sub-graph isomorphism, but I have some questions related to hypergraph adjacency matrix decomposition as well? The main issue is that I don't know the correct terms to search for.

[naive plover]

Let X be the six element set fx1; x2; x3; x4; x5; x6.
(b) How many subsets of X contain x2 and x3 but do not contain x6?

Is this 2^4?

[drowsy helm]

I think here is fine

[drowsy helm]

This might be easier to just count instead of compute rigorously, consider each case of how much the subset is |1| = 0 (not enough space for both x2, x3), |2| = 1 (just x2, x3), |3| = 3 (x2, x3, and either x1, x4, or x5) |4| = 3 (x2, x3, and 3C2 from the other 3), |5| = 1 (x1-x5), and |6| = 0 since it would have to have x6 => 1 + 3 + 3 + 1. You could alternatively consider this problem as 2 fixed points on only 5 elements (just get rid of x6). You may also notice the sum we did looks like Pascal’s triangle, not coincidental.

Cactus?

[naive plover]

yus

[weary tiger]

why in a set like {2,2,2} the number of elements is 1 not 3?

[obtuse lance]

sets don't really hold duplicates, {2, 2} is the same set as {2}

[weary tiger]

why set like { r E Z | 2 <= r <= -2 } has no elements and not { -2,0,1,2 } (4 elements)?

[drowsy helm]

Well 2<= r <= -2 doesn’t have anything in that range. You’re saying r is bigger than 2 but at the same time is smaller than -2 which doesn’t make sense

[inner marsh]

Hi!
it might be a lazy question but what does f[A] mean? (f : N -> N)

[inner otter]

what's the context?

[inner marsh]

f is a function from N to N

[inner otter]

yes, I got that from the notation. I mean the surrounding context, what's the whole problem/question

[inner marsh]

I need to prove that iff for each A, B which are different infinite subsets of N, f[A] /= f[B] is true, then f is injective

[ivory badge]

do you know what the image is

[inner marsh]

yea

is that the image?

I am used to it being simply notated as f(A)

[lyric quartz]

All those different notations and names.

[tulip cypress]

I know that |pA| = 2^m and |pB| = 2^n but I'm not sure how to go from there. I think that the number of total functions is just 2^(m+n) since each element of pA can choose |pB| = 2^n elements. I'm not sure if this is correct.

And I'm not sure how to even think of how many partial functions there could be

[tulip cypress]

nvm, I solved it.

[inner marsh]

I need to prove that a function f is surjective if and only if (f^-1)[A] /= (f^-1)[B]. isn't it enough to prove that if the function is surjective, then (f^-1)[A] /= (f^-1)[B] is true? because how can a function have an inverse if it's not surjective?

[cerulean wind]

what?

do you mean that f : X --> Y is surjective if and only if for every A,B subset Y, f^-1[A] = f^-1[B] implies A = B?

[weary tiger]

<@&286206848099549185>

the optimal solution they gave looks incorrect. it should be 1,2,5,4,7,8,3,2,5,9

[weary tiger]

@pulsar glade wanna have a shot at this?

[unreal stump]

Well the way I would do this is

for x in coffee:
   current_min = find_min(current_min, shortest (s,x)+shortest(x,t))

@weary tiger

Like shortest(s,x) would be finding the shortest path from s to x which can be found out with bfs

You can also keep track of path between s,x and x,t

Concat to get complete path

If current min reduces, update the complete path

This definitely corresponds to some reduction

[weary tiger]

but is that O(V+E)?

Also I think they want a different approach

[unreal stump]

Well you can pre compute everything

[weary tiger]

They said construct a new G'

[unreal stump]

So this reduces to O(V+E)

[weary tiger]

That works but the question definitely wants something different

[unreal stump]

What is the "standard reachability problem" exactly

Find the shortest path?

[weary tiger]

Yeah

Find the shortest path in an unweighted graph

We might have to do something with edges emanating from the coffee shops

When building G'

[unreal stump]

I think my approach is actually what they want

So construct a similar copy of G

find shortest path from s to some coffee shop x in original one

Find shortest path from x in the copy to t in the copy

Connect x to x in copy to get one candidate for shortest path

I guess you can modify this construction to find the actual shortest path?

[weary tiger]

"a new graph G′ with two designated vertices s′ and t′ such that a path from s′ to t′ in G′ correspond to a path from s to t that goes through a coffee shop in G."

The wording here seems to suggest something different

[unreal stump]

Here here t in copy is not same as t in original

[weary tiger]

Upper bound the number of vertices and edges in G′ and conclude that the problem can be solved in O(|V | + |E|) time, where |V | and |E| are the number of vertices and the number of edges in the original graph G

So would you say they want us to upper bound the vertices in G' with 2V?

[unreal stump]

Well I think it would be O(2|V|+2|E|)

[weary tiger]

which is the same as O(V+E) i suppose

[unreal stump]

Actually I think this works

If there is a path between s and t' , it should pass through x to copy x link

Because there is only one bridge between the 2 graphs

[weary tiger]

are you sure we don't have to multiply by the number of coffee shops

We have to make a new G' for every x

[unreal stump]

Well this is an example

But yea you need x copies

nvm you need one copy of graph. Link x to copy of x for all x

So it's like a bipartite graph

[weary tiger]

But will the shortest path in G' pass through x?

[unreal stump]

It has to

[weary tiger]

i think it will

[unreal stump]

All paths from s to t' will have to pass through some x to copy x link

[weary tiger]

since that's the only way the two graphs are connected

[unreal stump]

Because this construction is a bipartite graph with x to copy x links linking the 2 copies

[weary tiger]

I wouldn't say bipartite since that implies no internal connections but you're on the right track. There are two disconnected copies of G which can only be connected using the x links

[unreal stump]

mb, yeah

This new graph has 2|V| vertices and 2|E|+x edges

[weary tiger]

Therefore a path that goes from one component to the other necessarily goes through a cross edge

[weary tiger]

2E+x is possible to upper bound with 3E

well x<=V

Presumably G itself is connected

Blah blah there's probably a way to upper bound 2E+x with some argument

@unreal stump thanks for the help

[faint sage]

how would i solve this?

i know that 3x - 11y = 7

and that 8x - 9z = 3

solving for 3x-11y = 7 using EEA, i got x = -11n + 28

idk where to go from there

[weary tiger]

Chinese remainder theorem

3x = 7 mod 11
12x = 28 mod 11
x = 6 mod 11

[wooden mason]

prerequisites for learning about Tutte polynomials?

[weary tiger]

8x = 3 mod 9
64x = 24 mod 9
x = 6 mod 9

[weary tiger]

all numbers of the form 99k+6 should satisfy this

No need for chinese remainder theorem actually

[faint sage]

i got x = 6 mod 11 and x = 6 mod 9

but then how did you derive 99k + 6?

[weary tiger]

it's of the form 11(9k)+6 and 9(11k)+6

so it satisfies both congruences

[faint sage]

would it be different if the remainders were different?

[weary tiger]

yes

then it'd be a completely different game

[faint sage]

how would you go about it say if x = 6 mod 11 and x = 5 mod 9?

[weary tiger]

it would be x = 9.9'.5 + 11.11'.6 mod 99
where 9' is the inverse of 9 in mod 11 and 11' is the inverse of 11 in mod 9

[faint sage]

oh i guess i picked a bad example. like i meant how would you go about solving it

[weary tiger]

Literally like that

[faint sage]

ohhhh i see

[weary tiger]

I would go about finding 9' and 11'

then you plug those in and you get x equals to some number mod 99

[faint sage]

okay. Thank you so much!!

[slate ginkgo]

any good website/vid that can explain how i can find the explicit formula of a recursive formula?

where i start from a_n

[glacial lynx]

Hey would someone mind giving me a hint for discrete maths

The third equality

[tight hound]

This obviously depends on what the recursive formula in question is, there is no 'general' method that covers every possible case.

[plucky marsh]

Pascal’s triangle? 🤔

[queen flax]

hey-o! I'm having a really hard time grasping the concepts of (solving) recurrence relations, induction, and strong induction. Does anyone have any resources or youtube videos that they would recommend I watch? Most of the stuff i've tried hasnt really gotten through to me...

feel free to ping me w a reply ❤️

[vivid gust]

it’s not as easy as a+b=c, i already looked it and watched many videos and if it was i wouldn’t be asking people for help now would i? thanks for teaching me how to google search tho

oh look^^ not the only one struggling

[vivid gust]

me too me too fam lmk if you find anything

[glossy willow]

fair enough, but if you’re active on this server for long enough you tend to see a lot of people don’t try searching stuff up first

[glossy willow]

Do you have any answer keys to the problems you struggle with

[queen flax]

https://www.youtube.com/watch?v=pievWlIOgVc&list=PLl-gb0E4MII0sGLCJeqDB3y63HZ6lM5LJ&index=21&ab_channel=KimberlyBrehm

this playlist seems good!

using it rn to study

[thin vector]

https://rellek.net/book/ch_recurrence.html

^This is a good resource to learn recurrence equations

the textbook also has solutions to odd numbered exercises as well

[sacred fern]

Hi, I need help finding a particular solution to this recurrence relation

I have found the general solution which is $f(n) = c_1(-1)^n + c_{2}3^n + c_{3}n3^n$

[vital dew]

ForJoke

[agile magnet]

Have you tried to prove this by induction?

This + Pascal's identity should do the trick very easily

Well, easily assuming you know both those things

If you don't, I or someone else can help

[queen flax]

tyvm!

[jaunty thunder]

Where was this when I was failing lmao!!! Yall are so smart and I cant even

[sacred fern]

<@&286206848099549185>

[thin vector]

consider the RHS, now what $f_0$ do you think works here?

[vital dew]

oNatsyy

[sacred fern]

my first thought was something an^3 + bn^2 ngl

in my classes they haven't given a single hint of the intuition behind these things

[vivid gust]

yes but i struggle with fully understanding what’s going on

[small plume]

how should I approach these type of problems?

[jolly ledge]

Try looking for patterns (maybe you can express the values of each element of the sequence with other expressions which you know the formula for?), or use a telescopic sum

[meager mural]

how did they convert the geometric sequence to that explicit formula?

[small plume]

I got the first one, but stuck on the 2nd

[pulsar glade]

I guess the easiest is using differences of differences

[small plume]

whats differences of differences

[pulsar glade]

smth like this

Idk if that's how you call it. In economics, it means a different thing

[weary tiger]

Try writing each of the numbers using only the previous one and the previous previous one.

[jolly ledge]

Do you recall the geometric series formula?

[pulsar glade]

Or that

[small plume]

oh thats obvious now

[jolly ledge]

Fibonnaci be laughing

[meager mural]

the (r^n+1 - 1/r-1)?

[jolly ledge]

It's

[a \cdot \frac{1-r^n}{1-r}]

Where $r$ is the common ratio and $a$ is the starting term

[vital dew]

Kiameimon | Welt Rene

[jolly ledge]

Now how would you apply it to your question?

[small plume]

I retract my statement

I thought it was 2 * a_n - 1 + something but this pattern isnt making sense now

[weary tiger]

do this for numbers after the first two

you will see it soon enough

[meager mural]

3 is the common ratio and idk the starting term

[jolly ledge]

No, 2 is the common ratio as it the following is always multiplied ("scaled") by 2

And our first term is simply the number at n = 1, which is 3

[meager mural]

$$p_k = p_{k-1}+2*3^k$$
$$p_1 = 2$$

[vital dew]

DEVILWEARSPRADA

[meager mural]

was wondering how can i solve for the explicit formula for this problem

$$p_n = 2+23^2+23^3+23^4+....+23^n$$

[vital dew]

DEVILWEARSPRADA

[meager mural]

this is what i got up to. was wondering how can i get it to an explicit formula

also im not sure if it's suppose to be n or n-1 at the end

[weary tiger]

@unreal stump wanna give this a go?

[unreal stump]

My idea would be to start at a point,find all vertices reachable from that

Now pick a vertex not in the reachable set and repeat

Repeat till everything is in reachable set

[weary tiger]

but would that give the minimum?

[unreal stump]

Ok fair

[weary tiger]

that would give a possible solution but I don't think its optimal

[unreal stump]

You could start with a non optimal veryex

[weary tiger]

This almost looks like finding strongly connected components

But the restriction is looser

[weary tiger]

that might cause a problem with overlapping vertices

hmm I was thinking of doing as you said and then figuring out how to merge those components somehow

if one component points to another we can merge them

[unreal stump]

Actually yeah that was what I was thinking rn

[weary tiger]

That's probably beyond O(V+E) though

I wonder if the concept of a DAG can help somehow

you know when they contract the strongly connected components in a graph into a vertex for each component, it becomes a DAG

[unreal stump]

Actually I guess DSU might be useful here

[jolly ledge]

It's 3 × 2^k

Or are u solving a separate question

[weary tiger]

we didn't study those

[broken sonnet]

I was wondering if I could get some hints on how to describe this algorithm in a less verbose way

I understand that we can use DFS for something like this

[meager mural]

is 3*2^k the explicit formula?

[broken sonnet]

but I am having a hard time on how to describe it after we go from the source vertex a beyond the other vertices that are incident to it

[weary tiger]

topo sort uses DFS to find the finishing times. It is verbose but the point is you understand why topo sort is the way to go for this question

[jolly ledge]

For your question specifically, it's a sum (from 1 to n) of 3 × 2^n - 3× 2^(n-1)

So, using the formula you'll get

[weary tiger]

Essentially you're arranging the graph in such a way that all edges point right. This represents the flow from the source to the sink

[jolly ledge]

It's

[a \cdot \frac{1-r^n}{1-r}]

Where $r$ is the common ratio (2 in your case) and $a$ (3 in your case) is the starting term

[vital dew]

Kiameimon | Welt Rene

[jolly ledge]

And now, subtract 3×2^(n-1) from that

[meager mural]

yea that one was solved already. it was in the answer key. i just didn't understand how it came to that formula

but now i do

[jolly ledge]

Ahh kk so Yr one on 2 × 3^n is another qn?

[broken sonnet]

so in summary can I describe something such as we have vertices that are explored earlier pointing to vertices explored later in the sequence?

[meager mural]

the one i latexed is a diff question

[weary tiger]

@unreal stump I think if you keep merging the components you eventually get to a two layered DAG

[meager mural]

i basically got to the end. i'm missing like 1 step

check the image on top

[jolly ledge]

Why don't u try and figure out what a and r are gonna be in Yr other question?

[weary tiger]

you can't have a third layer cause you can just merge that layer

[jolly ledge]

Just apply the formula with an appropriate a and an appropriate r

[meager mural]

not sure. the chapter never taught us this. just iteration and some creative distribution using sum of geometric sequences/sum of first n integers

[weary tiger]

Do you understand how topo sort works? You're not just applying DFS like the way you said. You use DFS to find the finishing times and then sort the nodes by finishing time

[jolly ledge]

https://www.cuemath.com/geometric-series-formula/

This may help

[meager mural]

yes but can i turn this into an explicit formula
$$p_n = 2+23^2+23^3+23^4+...+23^n$$
just using distribution and the sum of geometric sequences.

[vital dew]

DEVILWEARSPRADA

[jolly ledge]

I'm not sure of the specific definition of an explicit formula

[meager mural]

its a solution to the recurrence relation

[jolly ledge]

Then yeah, it'll work

[spiral aspen]

help

how does this work?

if we have 3 seats _ _ _ I can have 101, 100, 010, 001 where 1 is occupied and 0 is not occupied

but F4 = 3??

[vestal bronze]

000

[spiral aspen]

ok but then we get 5 possibilities

but F4 is 3

[vestal bronze]

so you 're supposed to count like it's 5

hm

i don't know how they got n+1, but it's basically true

just read n+2

[spiral aspen]

ok so then i solve this question for Fn+2 instead of Fn+1

is that what u mean?

[vestal bronze]

yes F_{n+2}

[spiral aspen]

ok thanks! and i prove this by induction right?

[vestal bronze]

can't say

[spiral aspen]

its false but i cant think of a counter example

[small plume]

$$\sum _{i=3}^5\left(\prod _{j=1}^i\left(3j-2\right)\right):$$

[vital dew]

Pingu

[small plume]

how would you do this?

[cerulean wind]

just do it

compute the product for each i for i = 3, 4, 5

then add all of the products together

[small plume]

alr making sure I didnt have to do some extra step I was missing lol

[weary tiger]

Should I pick the minimum blue edge and the minimum red edge and start growing the tree from there using a greedy approach?

[mellow bronze]

Hello, is the last step (purple) necessary in this Karnaugh diagram?

the answer is no, but for some reason when trying to use Quine i get the purple implicant

if any1 answers tag me in the reply

[wide vine]

what is quinne

My understanding is the goal is to work with 2^n size groups pairs and enclose all the 1's. Anything else is then 0s As long as you have them all enclosed by some pairs any others are just redundant and wont change anything (ie not necessary)

I mean you could also do this whole process without a Karnaugh map if you would like

[small plume]

stuck on this

like what can I do to k! >= 3^(k)

[haughty garden]

Since n >= 7, you know that k > 3; in particular, (k + 1) > 3

[small plume]

why is k > 3 relevant?

[haughty garden]

Well your assumption is that the proposition holds for n = k

The point here is that (k + 1) > 3

And this helps to prove your proposition by multiplying both sides by k! and then employing the inductive hypothesis

[small plume]

ah I see thanks

[digital raven]

Isn't addition a function? Why is it sometimes called an operator?

Sorry if this is the wrong channel to ask such a question, where should I ask this question?

[coral parcel]

Operators are particular kinds of functions.

Or, perhaps more accurately, an "operator" in this context is a function that we're thinking of in a particular way.

[digital raven]

I think i just need more experience talking about this stuff, reading it, and doing it. I just realized I really don't know the difference between the two, and your explanation jives with my research, but at the same time the explanation doesn't jive with me because I haven't explored the particular ways i think about functions in such a way where the difference in terminology is useful to my understanding and mathematical communication. Perhaps when I finish my linear algebra course it will make more sense.

[coral parcel]

Beware that there are at least two different set of circumstances where we tend to call certain functions "operator".
In abstract algebra, an "operator" is generally something like "addition" or "multiplication" -- one of the functions that go together with an underlying set to make a structure (such as a group or a vector space). Most often you'll see the word "operator" used either about the abstract symbol such as "+" that name one of the "slots" in the definition of a whatever-it-is that you fill in with concrete functions to make an actual whatever-it-is. But it's not unheard-of to use that word about the concrete functions you fill the slots with.
In functional analysis, an "operator" is simply a linear transformation from a (often infinite-dimensional) vector space to itself.
To complete the confusion, either of these meanings might show up in a linear-algebra course.

[weary tiger]

How would you guys use the median selection algorithm and DFS to solve 6b) ?

<@&286206848099549185>

[weary tiger]

@unreal stump you know how to solve this?

[unreal stump]

Wdym by a median in context of graphs