discrete-math

[muted basin]

my brain is making me think these are inherently the same thing

[lethal linden]

The presence of a single unhappy person makes the former implication true, but not the latter.

[muted basin]

How though? doesnt Every unhappy person is tall just translate to false for “every person is happy” again

[lethal linden]

Ok, let P be "is divisible by 2" and let Q be "is divisible by 3".

It's true that: if every integer is divisible by 2 then every integer is divisible by 3.

Why is that true? Because the antecedent is false: there are in fact integers not divisible by 2.

On the other hand, the right side says: every integer divisible by 2 is also divisible by 3.

That's false.

[muted basin]

ah so I think I'm seeing where my problem is

I need to sort of "seperate" the other half of the antecedent (Q(x)) as its own thing

whereas the "Every" encompasses 1 single x for the second statement

I think the main problem is figuring out just how to word predicates to serve me properly

[lethal linden]

You can make the left-hand side true by picking a predicate that's not true for everything in the domain.

So, I dunno, make P mean "equals 2" and make Q mean "equals 3"

If every integer equals 2 then (blah)

That's true no matter what blah is

Because the antecedent is false

But it's definitely not true that for every integer, if it equals 2 then it equals 3

[muted basin]

while the right hand is "Every x that is equal to 2 is equal to 3"

and every x that is equal to 2 is just a true statement inherently, but how would I explain that?

the sentence makes sense to me

but we get to choose another value for the left to explain that the antecedent is false

[lethal linden]

For every x, if x = 2 then x = 3

That's false

Sure, maybe this is just a scoping confusion, but I think it's more than that.

I dunno.

[muted basin]

the statement makes perfect logical sense of course but what's throwing me out is the actual quantifiers

[lethal linden]

If we're sticking to the integers ∀xPx → ∀xQx means "If P is true for every integer then Q is also true for every integer."

The overall implication is true in two cases:

1. P and Q are both true for every integer
2. P is false for some integers

[muted basin]

right

[lethal linden]

While the right-hand side is saying that every integer which satisfies P also satisfies Q

[muted basin]

okay this makes sense

is it safe to assume this structure of sentence for any instance of universal qualifiers in a predicate?

If the scope is split between two values, the sentence structure fits the "if P is true for all x then Q is also true for all X" versus if the scope is the entire implication we can formulate it as "Every x that satisfies P also satisfies Q"

i guess not two values, but whatever the term is for P(x)

function / proposition

[lethal linden]

In terms of domains and whatnot, the general idea of interpretation is that you stipulate a set S which acts as the domain. Unary predicates like P and Q get interpreted as subsets of S and Px is interpreted as saying x is an element of the subset corresponding to P.

So, here S is the integers, P is the subset of all integers divisible by 2 and Q is the subset of all integers divisible by 3.

But we could also take the domain to be a two-element set {a,b}, interpret P to be {a} and interpret Q to be {b}

That's also a countermodel. If we imagine x ranging over {a,b} and Pz meaning z ∈ {a} and Qz meaning z ∈ {b}

1. ∀xPx → ∀xQx is true
2. ∀x(Px → Qx) is false

[muted basin]

ahhh okay im starting to understand more

[lethal linden]

If you have n-ary predicates they set interpreted as n-tuples of elements of S.

So something like R(x,y) is "assigned" (interpreted as) some subset of ordered pairs of the domain.

T(x,y,z) is interpreted as some subset of ordered triples

[muted basin]

so for ex. a subset of R(x,y) could be {(a,b), (b,a), etc}?

[lethal linden]

In the case of the domain being D = {a,b}, the set D^2 of ordered pairs is

{(a,a), (a,b), (b,a), (b,b)}

That's just some 4-element set. If we had a binary predicate/relation like R(x,y), we interpret R by choosing a subset of D^2 to assign it to.

Well, D^2 has 4 elements, which means it has 2^4 subsets. So there are 2^4 possible ways of interpreting R

[muted basin]

right right

okay im starting to understand it more

i was overcomplicating my ideas when reading you and bees stuff earlier regarding sets

[lethal linden]

Yes. Your book will cover that part eventually, I'm sure, but it's a bit weird to be asking for counter-models before talking about it.

By imagining the variables to be ranging over the integers and thinking up predicates, you're doing it implicitly.

[muted basin]

as for the proof sequences… im gonna try some of these other practices in hopes they arent as evil but i will talk to my professor about how on earth i was supposed to prove 18 given the rules i had

[lethal linden]

Like, saying Px means "x is divisbile by 2" corresponds to assigning P the set {n ∈ ℤ : n is divisible by 2}

[muted basin]

we started proofs with hoares logic and contraposition and etc and that has been far easier to grasp than the proof sequences wirh predicates and propositionals

thank you for bearing with me today

i appreciate it a lot

[lethal linden]

cheers

[vital dew]

Creeperarcade 2.0

[jade hollow]

"Say you're arranging 4 distinct pencils, 3 distinct markers, and 3 distinct erasers in some order into your pencil case, with the constraint that you cannot put an item in if there are already more of that type of item than another type of item. How many different orders are there for you to put the items in your pencil case?" could anyone help me solve this problem

I'm getting conflicting values between my work and an ai's

so I was wondering if anyone could give their answer to this problem

[short hare]

well well well

look who found it

[jade hollow]

😡

[short hare]

would you let me assist you kind sir?

[jade hollow]

no

😡

[short hare]

damn

😦

[jade hollow]

no but seriously can someone who actually knows how to solve this tell me their answer 😭

I got 186624 (prob not right)

ok I'll just move to an occupied help channel

[stray reef]

@jade hollow @short hare hey could yall not do this kinda banter in public please

[jade hollow]

lol sorry

[short hare]

mb i wont lol

[proven ibex]

<@&268886789983436800>

[shell jewel]

Hi, I was thinking about this and I don’t think this is true. The fact that all orbits are disjoint has nothing to do with the fact that p is prime, and it’s still true even if we simply assume that there exists some f: S -> S such that for every s in S there exists a n in N such that f^n(s) = s.

Not only we don’t need n to be prime, it doesn’t even need to be the same n for every element (n can depend on s).

Proof:

[quick folio]

Oh shit you’re back

[shell jewel]

Let $O(s)$ denote the orbit generated from a given $s \in S$ by repeated application of $f$. Suppose that there exist two orbits that intersect, which means there exist $s_1, s_2 \in S$ such that $O(s_1) \cap O(s_2)$ is non-empty.

Let $\bar{s}$ be an element in the intersection of these orbits. Since $\bar{s} \in O(s_1)$,
$$\bigcup_k , \left{ f^k (\bar{s}) \right} = O(s_1)$$
But $\bar{s}$ is also an element of $O(s_2)$. By applying again the result above, we get $O(s_1) = O(s_2)$.

So, if two orbits intersect, they’re actually just the same orbit. Which means that all orbits are disjoint

[vital dew]

Siupa

[shell jewel]

We didn’t use anything about n being prime, it also didn’t even need to be a unique single n for all the set S

[shell jewel]

Sorry I pinged you because you said we could continue again later

[quick folio]

No of course!

This is the kind of stuff I like doing

Good to know you didn’t give up on it

<incorrect messages deleted>

[fossil mural]

...no the proof is correct actually

$O(s_1) = \bigcup_k f^k(\bar s) = O(s_2)$

[vital dew]

bee [it/its]

[fossil mural]

both equalities are for the same reason: clearly $f^k(\bar s) \in O(s_1)$ (resp. $O(s_2)$), and conversely, for some $n$ we have $f^n(\bar s) = s_1$, and so $f^{n+k}(\bar s) = f^k(s_1)$

[vital dew]

bee [it/its]

[fossil mural]

or wait actually why are we writing it like this, that middle expression is just $O(\bar s)$

[vital dew]

bee [it/its]

[quick folio]

Yeah I definitely overcooked, thinking about it as a group action ironically led me to wrong conclusions

Then your proof should be complete

Good job on seeing through my bs

[shell jewel]

yeah 😅 true, the notation is already there why not use it

Thanks anyways! Glad to know I got it

[quick folio]

Prime is only needed to ensure that every orbit is divisible by p

[shell jewel]

yeah and since S is the union of F (the fixed points of f) and all the p-orbits, |S| = |F| + pN where N is the number of p-orbits, so |S| = |F| mod p.

I needed this little theorem because apparently it’s very useful for proving a bunch of other stuff in a simple and unified way (if you manage to construct the right f for the given situation, using this theorem you can prove Wilson’s theorem, Fermat’s little theorem, and a bunch of other stuff as a simple consequence)

[quick folio]

There is a (imo more straightforward) of understanding Wilson’s theorem and fermats little theorem through AA, but this is a good start

This result can also be generalised to functions f: S^n -> S^n, and non primes to say even more about S, but that is a little harder to understand without the prerequisite knowledge

[shell jewel]

Thanks, maybe I’ll look at it later if I have time

[quick folio]

Eh, I don’t think it would be worth it lmao

Just letting you know that the rabbit hole goes deeper

[shell jewel]

Yeah I suspect anything has a rabbit hole if you stare long enough 😅 anyways thanks for your time have a nice day

[trim thicket]

is one semester to learn discrete math unrealistic or is my question too vague?

[brave rock]

I would say that the total scope of "discrete math" is far too broad to learn in a lifetime.

If you mean to ask if it is possible to learn the content of a single discrete math course in a semester... yes, that is what a course does typically.

So I think that's about that.

[raven heart]

Check my proof pls

[stray reef]

<@&268886789983436800> troll

[full sonnet]

hii anyone know how to do mathamatical induction 2nd principle?

[stray reef]

no

none of us know what "2nd principle" is supposed to mean

[dreamy coral]

Apparently, it's strong induction

@full sonnet a pretty good proof for strong induction is to show that all natural numbers have a prime divisor

[tacit thistle]

Discrete math is what?

It’s the worst subject I have taken

[verbal pewter]

Yes

[verbal pewter]

Just say u didn't understand anything

[tacit thistle]

I understood some of it but the professor was terrible

[graceful shell]

agree

and we will have discrete math part 2 next year 😭

the sets are killing me

[tacit thistle]

i'm not a mathematician so i will avoid it 🙂

it's harder than calculus 3

harder than probability

[graceful shell]

and i cant because its "mandatory"

[full sonnet]

can someone help me with this

Problem 1. Prove that any amount of postage greater than or equal to 42 cents can be built using only 4-cent and
15-cent stamps.
Problem 2. any multiple of $10 that is $40 or greater.
Your bank ATM delivers cash using only $20 and $50 bills. Prove that you can collect, in addition to $20
i literally dont know how to do it. i know the first principle but not the second

[lethal linden]

Use induction on the total postage

[full sonnet]

I have to use induction principle 2 for both

Welp

[lethal linden]

That's some jargon specific to your class or textbook, so you have to tell us what "Induction Principle 2" is.

[lethal linden]

Alright, the latter is called "strong induction".

[full sonnet]

Can you show me how do i solve?

This is the example that my prof made

Example: Prove that the amount of postage
greater than or equal to 8 cents can be built
using only 3-cent and 5-cent stamps.

Base case: P(8): 3 + 5 = 8 which is true.
• In this case we will have to establish additional cases to prove this.
Hence, establish two cases P(9) and P(10)
– Why do we need to prove P(9) and P(10) separately?
– Because these are the base cases
• P(9): 3 + 3 + 3 = 9 and P(10): 5 + 5 = 10
• Inductive step: Assuming that P(r) is true for any r, 8 <= r <= k, we need
to show that P(k+1) is also true
• We have proved P(r) is true for r = 8,9,10
– So, we can assume that k+1 >= 11
• If k+1 >= 11 then (k+1)-3= k-2 >= 8,
– Thus, k-2 is a legitimate r value, hence, by inductive hypothesis, P(k-2) is
true. Hence, k-2 can be written as a sum of 3s and 5s.
• Adding an additional 3 results in k+1 as a sum of 3s and 5s.
• This verifies that P(k+1) can be a sum of 3s and 5s and hence completes
the proof.

I copied it from the slides

[full sonnet]

.

[agile magnet]

Is your only question this?

Why do we need to prove P(9) and P(10) separately?

[full sonnet]

becuase of base case?

[agile magnet]

I'm not asking you to answer your own question

[full sonnet]

ion knoww

[agile magnet]

I'm trying to figure out what you do or don't understand about the proof

[full sonnet]

how do i prove

[agile magnet]

Do you understand the rest of the proof, just not why you need multiple base cases?

[full sonnet]

no i dont understand how to prove using that principle

[agile magnet]

do you understand how induction works?

[full sonnet]

kinda?

i know how to do with the first principle tho

[agile magnet]

Ok so lets study this proof more closely

what is "the first principle"?

[full sonnet]

like from here

[agile magnet]

oh I see

sorry I missed that earlier picture

Ok so all that changes is that you now assume more than just the prior case in the inductive step

so you get more stuff to work with

this is useful because in this proof, you need to use P(k - 2) to prove P(k + 1)

you can't use P(k) alone to prove P(k + 1)

or well, maybe you can but it would be much much harder, I don't even know how to do that

[full sonnet]

this is how my prof did

[agile magnet]

yea I know I can see

and I am trying to help you understand that proof more

[agile magnet]

Ok so if P(8) was our only base case

Then when we do the inductive step, we can only say that k + 1 >= 9 right?

[full sonnet]

yes

[agile magnet]

So then k - 2 >= 6

and we don't know if P(k - 2) is true if k - 2 = 6 or 7

in fact, P(k - 2) is false if k - 2 = 7

right?

you cannot create 7 cents using only 3 cent and 5 cent coins

So we need to say that k - 2 >= 8 to be able to apply our inductive hypothesis

meaning that in our inductive step, we have to assume that k + 1 >= 11

and so we cannot have P(8) as our only base case, we also need P(9) and P(10)

Does this make sense? If not that's fine, tell me what is confusing you.

[full sonnet]

why 11 tho? can i chose other number?

[agile magnet]

what other number would you like to choose?

We can figure out if it works or not

[full sonnet]

like 17?

[agile magnet]

Sure

if we assume that k + 1 >= 17 in our inductive step

the rest of the proof would go through as normal

and we would need to already know that P(k - 2) is true for k - 2 >= 14

and so we need P(8), P(9), ..., P(14) as our base cases

so you can do this, but then you have to prove a ton more base cases

which is more work, and who wants to do more work?

[full sonnet]

for this step how did u get k -2

[agile magnet]

just following the proof that was written in the slide

[full sonnet]

hmm ok so for this question how do i solve

[queen spire]

Just started Discrete Math yesterday, I'm kind of amazed at how broad this branch of math is, from propositional logic, to discrete probability, graph theory. etc. I probably should have learned this class before Calculus, lol.

[hidden totem]

yeah discrete math is severely underrated and underappreciated imo

like all of counting is under the umbrella of discrete math and some of the hardest and deepest problems in all of mathematics are there

[valid thicket]

can't wait to take a enumerative combinatorics class

[pseudo sigil]

anyone wants to start a study group for discrete math? guided by the book: Discrete
Mathematics and Its Applications by Rosen or something?

studying cs and this course really is something

[marble gust]

about seating arrangements on a round table, do i just replace n! with (n-1)! for every term in an expression that describes a row of seats?

[valid thicket]

send the question

[muted basin]

confused by professors solution

why is the induction step started with the induction conclusion

wouldn't the first step be P(n) + P(n+1) here

so n^3 + 2n + (n+1)^3 + 2(n+1)

also, where did he get the 3 as a factor for n^2 + n + 1

I understand the final line where 3x is brought out from n^3 + 2n = 3x but... nothing else here lol

[lethal linden]

P(n) is a proposition, like "n is divisible by 19".

What does 19 | n + 19 | n+1 even mean?

[muted basin]

n = 19k + (n+1) = 19k

[lethal linden]

??

[muted basin]

I was just using the formula for divisors we have

[lethal linden]

Let P(n) mean "there are n people in the room right now"

[muted basin]

it just states a|b is b = ak for some int k

[lethal linden]

What does P(5) + P(6) mean?

You can't add propositions. P(n) + P(n+1) is nonsensical.

[muted basin]

but isn't that how induction is done commonly?

[lethal linden]

No.

You assume P(n) and prove P(n+1) under that assumption

[muted basin]

Like for example, if we're doing induction on a summation we make our conclusion from P(n+1) but when we do the induction step, we do P(n) + n+1 step

If the summation is like 1 + 2 + 3... n and we are trying to prove that this = n(n+1)^2 or some random arbitrary formula

[lethal linden]

Nope. You're confused about the nature of induction.

[muted basin]

our induction hypothesis is 1+2+3... n

our induction conclusion is (n+1)(n+2)^2

and we start induction step with P(n) + one step up

here it would just be n+1

if it was like 1+2+3.... n! for example it would be P(n) + (n+1)!

so first step would be n(n+1)^2 + (n+1)!

the induction conclusion in this particular problem is that (n+1)^3 + 2(n+1) = 3x

[neon harbor]

1+2+3+...+n can't be a hypothesis, that's just a sum. Are you familiar with the difference between a proposition and an expression?

[muted basin]

I left out the rest my bad

The hypothesis would be that that summation is equal to whatever we're trying to prove

in the example I typed up it would be sum(n) = n(n+1)^2

in the example in the photo the IH would just be the statement itself

3 | n^3 + 2n

[neon harbor]

that's not something you can just leave out, it's nonsensical to write "the hypothesis is 1+2+3+...+n", and it makes it impossible for us to know what you do or do not understand about induction

[muted basin]

sorry

[neon harbor]

it seems like you're thinking about induction as something to do with sums specifically. What exactly is P(n) + P(n+1) supposed to mean when P(n) is a proposition?

[muted basin]

induction through sums is just what I'm most accustomed to so far in practice

induction through inequalities and propositions like this are a struggle for me

wouldnt it just be that the n+1 is subbed in for our original hypothesis but is still meant to be equivalent to what is implicated

idk if that wording is right

there's not exactly a +1 step since it isn't summation

[lethal linden]

The professor is trying to make sure you're absolutely clear on what P(n) is before proceeding.

You assume P(n) and use that assumption to prove P(n+1).

What is P(n) in your case?

[muted basin]

n^3 + 2n = 3x for some x

[lethal linden]

Yes, it's that 3 | n^3 + 2n

What's P(n+1)?

I guess it's written down, so you could just be copying it.

What's P(4)?

[muted basin]

4^3 + 2(4) = 3x ?

[lethal linden]

It's the proposition that 3 divides 4^3 + 2*4

[muted basin]

4*3?

[lethal linden]

Sorry, typo

[muted basin]

ah gotcha

[lethal linden]

Ok, if we know that 3 divides n^3 + 2*n then can we prove: 3 divides (n+1)^3 + 2*(n+1)

[muted basin]

intuition says yes but I don't know how to answer why besides just going through induction

[lethal linden]

That's what your professor does. He assumes that 3 | n^3 + 2*n, i.e., that there exists a natural number x such that n^3 + 2*n = 3x

[muted basin]

in this example here he uses the IH as the base for finding the conclusion

we use the hypothesis and manipulate it so that we get the conclusion to prove it

but in the example I sent before is it because the conclusion involves an '=' that he uses (n+1)^3 + 2(n+1) ?

[lethal linden]

There will be some point (maybe multiple points) where you use the induction hypothesis to perform a step in your reasoning, yes.

No....

There's no...

Induction doesn't care about equality or inequality or sums.

There's not one thing you do for one, another thing you do for another.

You assume P(n), i.e., that 2^{n+2} < 5^n

And then use that assumption to prove P(n+1),i.e., that 2^{n+3} < 5^{n+1}

[muted basin]

right but then why isn't the induction step started with n^3 + 2n = 3x in the other example since thats the assumption we have

we use that assumption and manipulate it to arrive at our conclusion

but in the other he just uses a part of the conclusion as the first step

[lethal linden]

So you get...well:

2^{n+3} = 2 * 2^{n+2}  (definition of exponentiation)
        < 2 * 5^n      (inductive hypothesis + hint 2)
        < 5 * 5^n      (by hint 2)
        = 5^{n+1}      (definition of exponentiation)

[neon harbor]

The induction hypothesis P(n) doesn't have to be literally the first thing we write down when proving P(n+1). In your first example, we started with (n+1)^3 + 2(n+1) = (n+1)(n^2 + 2n + 1) + 2n + 2, which is always true, then we used P(n) later

[lethal linden]

Why would it be? It's going to be a fact you use to justify one or more steps in your reasoning. You choose when and where to make use of it.

[muted basin]

i guess that's where i was confusing myself, all the other examples follow a similar step by step process so I just assumed it'd have to be the same here

[lethal linden]

Share one of those examples

[lethal linden]

Sure, ok.

I can rewrite what I just wrote in that style.

[lethal linden]

The induction hypothesis P(n) is:

2^{n+2} < 5^n

Multiplying by 2, we get:

2 * 2^{n+2} < 2 * 5^n

Then, since 2 < 5 we have

2 * 5^n < 5 * 5^n

Therefore we have

2^{n+3} < 2 * 5^n < 5^{n+1}

which is P(n+1).

[lethal linden]

And I will rewrite this in the "equational" style:

(n+1)! = (n+1) * n!     (definition of factorial)
       < (n+1) * n^n    (induction hypothesis)
       = n*n^n + n^n    (distributive property)
       = n^{n+1} + n^n  (def'n of exponentiation)
       < n^{n+1}

The last step is justified because a < a + c if a, c > 0, whatever name you want to give that.

The equational style isn't always available, but it often makes thing clearer. Each line has its own justification. You wouldn't normally need to say things like "def'n of exponentiation" and "distributive property", etc. It'd be clear from the difference between lines what the justification was.

But that's really a judgement call based on your reader's expectations (here, your professor/grader). You'd definitely want to say where you relied on the inductive hypothesis.

[muted basin]

I guess I'm just still stuck on why he used the assumption of P(n+1) outright

It makes sense that he would want to prove that = 3x

[lethal linden]

He didn't use that assumption.

He just wrote down an expression.

[muted basin]

i see, and because this expression is just always true / valid, he expands it as to find that it can be formatted as 3x?

[lethal linden]

(n+1)^3 + 2*(n+1) is just some expression

No.

[lethal linden]

Expressions can't be true or false.

If 5 + 4 true or false?

What does that even mean?

[muted basin]

they just 'are' ?

[lethal linden]

Yes.

[muted basin]

gotcha

[lethal linden]

(n+1)^3 + 2*(n+1) is just some expression. He wants to show it's divisible by 3 because that's the content of proposition P(n+1).

[muted basin]

in that case, following this process, this might just be me brainfarting but where did the 3 come from in the 2nd to last step ?

[lethal linden]

So, he needs to be able to find some k such that (n+1)^3 + 2*(n+1) = 3*k.

[muted basin]

n^3 + 2n = 3x so it makes sense that he re-arranged the terms so that it can be used like that

wait

i just didnt add lol

3n^2 + 3n + 3 is factored

i see

[lethal linden]

?

[muted basin]

ignore me abt the step i mentioned in that image, I didn't add the like terms together and assumed he pulled the 3 from something else

[lethal linden]

He's skipping more steps that I would if my goal were to teach induction.

He wants to somehow get n^3 + 2*n by manipulating (n+1)^3 + 2*(n+1), because then he can use the induction hypothesis.

P(n) is that n^3 + 2*n = 3k for some natural number k.

[muted basin]

do you have any resources you'd recommend for drilling in contraposition / contradiction / induction? the solutions he makes don't exactly help me understand the fundamentals and our textbook is similar in simplifying the explanation too much leading to hard examples with very brief solutions that go from step to step without explanation

I'm not as confused about contraposition / contradiction since they have well defined WFF definitions ( P -> Q into -Q -> -P for example)

[lethal linden]

Using only basic algebra, he gets

(n+1)^3 + 2*(n+1) = (n^3 + 2n) + 3*(n^2 + n + 1)
                  = 3*k + 3*(n^2 + n + 1)
                  = 3*(k + n^2 + n + 1)

where the second = is justified by the induction hypothesis.

[muted basin]

but figured I'd ask for all 3 since they come hand in hand as proof techniques

[lethal linden]

I mean...

I don't think more drilling is what you need. You seem to be drilling bad habits.

The nice thing about the equational style is that you can stop at any line and ask yourself: "What did the author use to go from the previous line to this line?"

Like, up until x appears above, everything should register as basic algebra.

[muted basin]

right

[lethal linden]

Now suddenly x appears. You should ask: "How did that get there? How is the previous line equal to this line?"

There's nothing stopping you from seeing 3*(x + n^2 + n + 1) and imagining 3x + 3(n^2 + n + 1), i.e., distributing the 3.

And if you see 3x you should go, "Oh, we know that 3x = n^3 + 2n by the inductive hypothesis."

Or, likewise, your eyes should light up when you see n^3 + 2n because that's the moment when you could use the inductive hypothesis, which tells you that you can replace n^3 + 2n with 3x

[muted basin]

understanding the algebra has honestly probably been my weakest point for arriving at the conclusion

induction with summation has just been easier since you don't usually always have to introduce anything in like inequality problems where 2 is multiplied by both sides or this other problem

my creativity i think is lacking lol

[lethal linden]

Like...I can write the summation proof using the equation style, too.

Let P(n) by the statement that 1 + 2 + ... + n = n*(n+1)/2. Then

1+2+...+n+1 = (1+2+...+n) + (n+1)
            = n*(n+1)/2 + (n + 1)       (by inductive hypothesis)
            = n*(n+1)/2 + 2*(n + 1)/2
            = (n*(n+1) + 2*(n + 1))/2
            = (n^2 + n + 2n + 2)/2
            = (n+1)(n+2)/2

[lethal linden]

There's nothing special about inequality. You are attributing the difference in difficulty to inequality, divisibility, etc. because that's the difference in form that stands out most to you.

All the previous ones involved equalities and summation. I could do those.

These ones involve inequalities and things other than summation. I can't do these.

Therefore I can't do these because they involve inequalities and things other than summation.

That structure is a classic post hoc fallacy. X changed and Y happened, therefore the change in X caused Y.

[lethal linden]

The fact is, you do this all the time with equality and just don't think twice about it.

Like, if you saw a + 2 = b + 2, you'd think "Subtract 2 from both sides and conclude a = b."

You wouldn't even think, probably. It'd be more like a pre-rational reflex, something you've built up over years of schooling.

[muted basin]

thats fair, I suppose my mind is more shut off to inequality operation since introducing things in equalities aren't as super common

the most I can think of to introduce things in equalities would be getting a common divisor for example

[lethal linden]

I think it's the opposite. Your mind is shut off when you're dealing with equalities and your algebraic habits are good enough that it doesn't lead you astray.

But now you can't rely on those automatic habits and have to think about each step, what exactly is justifying what, etc.

[muted basin]

heres an example I did from my textbook

where I was struggling a while to understand each step in the process

(granted im not sure if this solution is even correct)

but I sort of brute forced my way through it with assumptions

[lethal linden]

But you are introducing something when you see a + 2 = b + 2 and conclude a = b. You're saying:

a + 2 = b + 2

Therefore

a + 2 + -2 = b + 2 + -2

Which means

a + 0 = b + 0

Which means

a = b

You just compress that all into one automatic step and don't think twice about it.

[muted basin]

I struggle to understand the "Why" of why something is less than so I just go with it

[lethal linden]

You are done as soon as you write

(n+1)! > 3^n * (n+1) > 3^(n+1)

But that's only true if (n+1) > 3, so that you get

(n+1)! > 3^n * (n+1)
       > 3^n * 3
       > 3^(n+1)

And if n > 7 then certainly n + 1 > 3, so you're fine

Everything else in your proof is unnecessary. You're relying on the fact that n+1 is positive.

[muted basin]

I start to get lost in the details when I have intermittent expressions in between the left hand side and right hand side

why is 3^n * (n+1) > 3^n+1 ?

I guess I could go through it with some cases but

surely at a certain value there is a chance that this statement doesn't hold

[lethal linden]

You're the one who wrote it! Or were you copying something from your textbook?

[muted basin]

textbook

[lethal linden]

I see.

Look, ultimately this is the difference between writing a > b > c rather than a > b and b > c

But, you have the following equalities and inequalities:

1. (n+1)! = (n+1) * n!
2. (n+1) * n! > (n+1) * 3^n
3. (n+1) * 3^n > 3 * 3^n
4. 3 * 3^n = 3^(n+1)

(2) is true if n! > 3^n, which is the inductive hypothesis.

(3) is true if n + 1 > 3, which is true because we're assuming n > 6.

And (1) and (4) are true just from the definition of factorial and exponentiation, respectively.

[muted basin]

ohhhh okay

so like you said i really didnt even need to divide by 3^n

[lethal linden]

Correct. It's clear you're trying to massage the thing into a certain shape, a shape you (incorrectly) associate with being what a "proof by induction" looks like.

The shape doesn't matter. It's the reasoning that matters. The shape is there to make the reasoning clearer, easier to follow.

Like, oh, I have 3^n on both sides of the inequality and therefore my automatic algebra brain says divide both sides by 3^n. That's the rule.

Well, ok, where your automatic algebra brain was previously serving you well, now it's not. That's fine — recognize when autopilot is helping and when you need a manual override.

[muted basin]

i think i get very stuck in black and white thinking where one side is the automation and I do stuff based off patterns

whereas the other side is me not being able to apply that

[muted basin]

and struggling to think of what to do on a fundamental level

then I hit that roadblock and make dangerous assumptions based off what i "do know" from a previous pattern but it just leads to misconceptions

[lethal linden]

You have to have your eye on the prize. In the case of a proof by induction, you have some proposition P(n) that will involve certain expressions.

P(n+1) will involve other expressions. You want to somehow take the statement of P(n+1) and isolate/precipitate/crystallize something from it that you can apply P(n) to.

If we're talking about n! > 3^n then we want to take (n+1)! > 3^(n+1) and find ways to get just n! and/or 3^n.

Well, ok, that's easy because of how factorial and exponentiation are defined. Factorial itself is defined recursively, so that (n+1)! = (n+1) * n! by definition. You can get n! from (n+1)! immediately.

In the case of the divisibility proof, you're starting with (n+1)^3 + 2*(n+1) and want to somehow get n^3 + 2*n, so that you can apply the inductive hypothesis.

Hopefully the context where it's applied means everything just works after that. That's not always the case, though. You might need to apply it and then do a bit more work, or find a different way to apply P(n).

[muted basin]

that's where I think most of the battle is for me

I'm either overcomplicating the idea of P(n) and P(n+1) in context of induction or just not understanding it fully

[lethal linden]

For these basic proofs it's almost always just algebra. You have some expression you can expand or simplify and out comes the relevant expression.

The point is to know what you're looking for rather than mindlessly carrying out an algorithm.

[muted basin]

It's easy to explain in summation problems as n+1, etc. is a common practice in calculus 2 problems

I'm going to try some more textbook problems that involve inequalities or equalities and see if I can try to apply what we've discussed and open my mind a little bit more / play around with the formulas

I think I have a little bit better of a grasp but only one way to find out lolol

thank you again for the help 🙏

[lethal linden]

Cheers

[vital radish]

does anyone have a reference on or know how to find the number of ways to tile an n x n toroidal grid k colors such that each row and column is aperiodic

[cursive dew]

The forallx logic book is open source right? So I can ask about thing from it without copyright issues? Just making sure.

[trim thicket]

i dont understand the last bit
how does (1/(2n+3))(1/(2n+4)) ever turn into 1/(n+3), which would satisfy the equality?

[fossil mural]

yeah this proof is complete nonsense and also the statement is false

[trim thicket]

lmao

damn frick ive misremembered the problem then because it was definitely solvable on the test 😭

[fossil mural]

maybe it was $\prod_{i=0}^n \left(\frac{1}{2i+1} \cdot \frac{1}{2i+2}\right) = \frac{1}{(2n+2)!}$?

[trim thicket]

oh wait that looks right actually

[vital dew]

bee [it/its]

[trim thicket]

lmao it looks like this one makes way more sense

aww thank you

also,
how the heck is that possible how did you even come up with that from my wrong thing???

[fossil mural]

it's still missing a base case but yes this proof does actually work now

[fossil mural]

well i just thought about what expression is equal to that product on the left, and that's what i came up with

[fossil mural]

also, arguably more of a stylistic thing, but using = on propositions is... weird
especially in this case where a statement like $P(n+1) = \frac{1}{(2(n+1)+2)!} = \prod_{i=0}^{n+1} \left(\frac{1}{2i+1} \cdot \frac{1}{2i+2}\right)$ kind of looks like a chain of equalities but actually isn't

[vital dew]

bee [it/its]

[fossil mural]

...possibly i'm oversensitive to this in particular because of the number of people here who might write something like that and mean it as a chain of equalities, because they don't understand that the inductive hypothesis is a proposition and not an expression

[trim thicket]

oh? its weird? i didnt know ;_;
i was just being lazy and trying to redo a question i saw on a test i did earlier
how would it be defined normally then

[fossil mural]

well the most obvious answer is symbols like $\iff$ or $\leftrightarrow$, which are pretty much just the equivalent of $=$ but for propositions

[vital dew]

bee [it/its]

[fossil mural]

but in this case i would probably just, use words

"Define P(n) as ..."
"P(n+1) is ..."

[trim thicket]

so

it would be

wait ill type it out

?

[fossil mural]

yeah

(to be clear this isn't something where anyone would really say your original proof was incorrect, it's more just that your original proof might have been confusing for half a second before the reader figured out what you meant)

[trim thicket]

whats the difference between Define P(n) as vs Let P(n)=
?

[fossil mural]

in terms of what they mean, absolutely nothing

but like, if you randomly decided to write the entire proof in red text, that wouldn't change what it means, but it's still a bit confusing for a human reading it, right?

and it's the same sort of difference here, a human reading the proof will draw the exact same conclusions about every aspect of what argument you're making but won't get momentarily confused by their brain automatically parsing "P(n) = ... = ..." as a chain of equalities and then having to consciously correct that

[trim thicket]

well tbh i kinda wanna know if there's like a minute pedantic difference
cuz im just curious

and also i wanna be able to go "erm actually 🤓 " to my other classmates who dont care about the class /hj

[fossil mural]

even trying to be pedantic i think there basically just isn't

...maybe in some context where "=" had a specialised meaning? but this... isn't that

and honestly if you zoom in far enough you just end up at "these are english words so they're intrinsically a bit fuzzy, the goal of a proof written in english is really just to successfully communicate the idea"

[graceful shell]

math is not mathing

what is n^+?

i can't type it literally

[uneven violet]

You mean $\mathbb{N}^+$?

[vital dew]

OneTrackPony

[graceful shell]

Yes

Wait no

It just normal small n

[uneven violet]

Ok, what is n in this context?

[graceful shell]

Positive number

Natural

[uneven violet]

Ok, I don’t know what that is. Can you provide the sentences where this is used?

[bronze spire]

positive natural numbers? then just 1, 2, 3, … etc

maybe they just use a different symbol for it

,w n^+

,w natural numbers

[trim thicket]

why would $\mathbb{N}^+$ ever be specified with that +? i thought all natural numbers are positive?

[vital dew]

2ndchar

[brave rock]

Some people like to include 0 in the natural numbers. There is no clear winner amongst mathematicians as to whether or not 0 should be included.

[trim thicket]

so $\mathbb{N}^+$ is just to exclude 0?

[vital dew]

2ndchar

[brave rock]

Yes.

[brave rock]

This isn't any kind of standard notation that I know. Whatever source you are reading from has likely defined this somewhere. You should either look for where it was defined, or share the context with us so we can try figuring out if, for example, it is a typo or something else.

[trim thicket]

this reminds me of that time i heard a math video say that some people in the past thought 0 was evil and unnatural so they avoided it
eugh why its literally nothing

[brave rock]

Zero is not literally nothing.

[trim thicket]

interesting

[brave rock]

People have always had strange ideas about numbers. There are plenty of people who will still argue that 0 is not a number. Mathematics doesn't really care.

It doesn't really matter whether or not we include 0 in N or not, as long as it's clearly communicated.

[graceful shell]

i see

hold up

n plus

[brave rock]

Probably means the successor of n.

You are learning, presumably, from the Peano axioms of arithmetic

[graceful shell]

yes

[brave rock]

There you go then

[graceful shell]

i see

[graceful shell]

you are so smart

damn

i can't even remember what i learnt half years ago

[mental rampart]

Can someone help me work out how the logic in the following problem's answer works? I can't seem to grasp how it develops its argument

[lethal linden]

Where does the proof stop making sense?

[mental rampart]

I'm reviewing now and I see that firstly I made a wrong assumption that 45 was the max number of matches for the month and not per day. Still, I can easily logically work out until ai-aj=14 -> ai=aj+14 but I'm trying to see how I would logically connect that to the pigeonhole principle

[lethal linden]

The plain PHP would just say that among those 60 numbers, each of which is between 1 and 59, two must be equal. 59 pigenholes and 60 pigeons.

But that would be true if, say, a_1 = a_2

The fact that a_1, ..., a_30 are distinct means none of those are equal to each other. It also means none of the a_1 + 14, ..., a_30 + 14 are equal to each other.

So, for two things among those 60 to be equal, one number must come from the former list and another number must come from the latter.

Like, if all of the a_1, ..., a_30 are red pigeons and the a_1 + 14, ..., a_30 + 14 are blue pigeons then them being distinct means we can say:

1. Every pigeon is red or blue
2. No pigeonhole contains two red pigeons
3. No pigeonhole contains two blue pigeons

Therefore, if a pigeonhole has more than one pigeon in it, it must be one red and one blue pigeon.

[mental rampart]

That makes sense, but why do we take the sequence an to be distinct in all its terms in the first place? I have a vague feeling that it's bc it's the case where we delay the fulfillment of the equation ai=aj+14 as much as possible but I'm not sure

[lethal linden]

We want a sequence of numbers where the boxes are defined by equality.

It's not uncommon if you have a sequence a_1, a_2, a_3, ... that you define a new sequence based on some fact about everything up to that point.

Like, define a new sequence b_j to be the sum of the first j things. The largest among the first j things. The smallest. etc.

So, here you might imagine g_1, g_2, g_3, ... being the number of games played on day 1, day 2, day 3, etc.

Then a_i really is just the sum of g_1 + ... + g_j

Because g_i >= 1, you have a_i = a_j iff i = j.

[mental rampart]

ohhh, wait so I understood correctly that the maximum games per month was 45, but misunderstood what a_i was, since it was the games played until that point and not the games played on a given date, I see. Then it's true that all its terms are necessarily distinct

[lethal linden]

Yes.

[lethal linden]

Gotta read closely! Math textbooks become less and less forgiving in this regard.

It says "on or before" and it relies heavily on that.

Try to recognize when you're mentally "auto-completing" things and find a way to read it again in a way that forces you to pay attention differently.

Here, you might write out what you think it's saying symbolically, on your own, and then compare what you wrote to what's on the page.

If you wrote a_i = games on day i and then went back to the text to double-check, you'd probably notice it said something different.

Haha. Well, there's an Alan Kay quote I wanted to share, but it has a banned keyword.

“A change in perspective is worth 80 brain points.” — Alan Kay

[mental rampart]

Thanks for the advice, and for the help, it really was handy, I'll get back to studying then

Also, "brain points" lmao

I think I know what the banned word is hahah

[marble gust]

anyone knows what the H in nHr stands for? and why does this notation not seem to be widespread unlike nPr and nCr?

and whats the relationship between unordered sampling with replacement(sample as many times as you want) and the amount of integer solutions of x+y+z = 5? theres a definition of nHr that relates it to matrices while my notes relate it to stars and bars so im so confused

[frosty verge]

Hi

[frosty verge]

Why 0! Is 1?

[marble gust]

theres only 1 way to arrange an empty set

[frosty verge]

Does it have any proof besides of this?

[marble gust]

its a function made by mankind you can think of it having some domain [1,inf)

but 0! looked useful so we gave it a definition too

and it fits n! = (n+1)!/(n+1)

[frosty verge]

Thank you

[marble gust]

np

[marble gust]

bump

now i get it: picking between n choices for r times requires the amount of each choices picked to sum up to r total picks

[trim thicket]

i feel like im going down the wrong path here....

[crystal jasper]

does x! count as discrete math

[neon harbor]

It's hard to see from your attempt which inequalities you have proved, and which ones you are trying to prove. If a certain inequality is a goal you're working towards, write just Goal: or a question mark above it or something.
After adding 1/sqrt(n+1) to both sides of the induction hypothesis, you're left with sqrt(n) + 1/sqrt(n+1) on the left. If you can show that sqrt(n+1) is less than this, you're done. To do this, you might need to square both sides

Btw, there's a direct proof of this that I think is easier than induction

[weary tiger]

Would the union in ZFC of {A,{A}} and {B,{B}} be {∀z ∈ A, A, ∀q ∈ B, B} ?

[pliant horizon]

is there a smart way to do this?

besides a brute force truth table

wait uh... the first row eliminates a and c...
p=q=r=T then

• a and c should be vacuously true. contradiction
  maybe there's a way to eliminate d

wdym?

[weary tiger]

nvm it was still a bit brute force like

[cerulean radish]

Noticing some patterns in the truth table can be useful as well; In this truth table the output is (not r) given p is true, see which of the expressions in the options satisfy that property (i.e., which ones simplify to (not r) when you let p = T)

Though at some degree this is also brute force combined with luck

[neon harbor]

Stupid question, but in a truth table, equivalence and biconditional is the same, right? <=> vs <->

[weary tiger]

equivalence is a biconditional that is only true (a tautology) from what I remember
so they can be the same but dont have to

[opal haven]

Tweaking and Geeking

because ive gotten to the point where stuff makes less and less sense the more I try to pay attention

[hidden totem]

so here's the thing

the smarter the method, the less "describable" it is

the more brute forcey it is the easier it is to explain step by step how to do it

do you want an explanation that is slick but only applies to this problem

or do you want a brutey way that can handle anything

or do you want something in between, sorta general but also a bit wishy washy

[marble gust]

random thought about permutation:

if the number of arrangements of r objects from a set of size n is nPr, and the number of arrangements of n objects with r indistinguishable objects in it is n!/r!, then whats the number of arrangements of r objects from a set of size n, where the set houses k indistinguishable objects?

[marble gust]

How many different patterns are there when 4 letters are taken from {A, A, A, A, B, B, C, D, E, F} to form a 4-letter string?

[valid thicket]

This seems hard

[hidden totem]

there isnt a simple formula for this, and to see why, it helps to understand the bijection between the first two examples you gave

to arrange r objects from a set of n, you are making separate individual choices about which object to pick

for instance, out of 6 objects 1-6, suppose we want 3, pick, in order: (3,2,5)

to arrange n objects where r are indistinguishable, pretend that we totally ignore the r indistinguishable objects, we simply place the other objects by independently selecting which positions the objects go in, filling in the unselected positions with the indistinguishable objects

for example, with 6 positions 1-6 to place 6 objects, 3 of which are indistinguishable, we could pick (3,2,5) and that would give us the arrangement X,B,A,X,C,X

so the bijection is to simply take the ordering we chose and assign them to the positions, or to reverse this process by listing in order the positions to obtain the ordering of the objects

one selects by object index, one selects by positional index

the problem you posed is difficult because it combines dependencies of both properties into the same problem

but that doesn't necessarily make a problem difficult. here is exactly what makes it difficult:

you have n-k distinguishable objects. first pick how many positions out of the total r are the indistinguishable objects, let's say this is called i. this gives rCi. the remaining r-i positions now need to be filled with the distinguishable objects. (n-k)!P(r-i). multiply these counts and sum over i from 0 to k

$$\sum_{i=0}^k \binom{r}{i} \frac{(n-k)!}{(n-k-r+i)!}$$

[vital dew]

Cozmogrgdfschkipkhrshtensi

[hidden totem]

this sum cant really be simplified, so it is quite messy

even in the case where your k is at least r, this does not give you a closed form

although relatively speaking, compared to other combi problems, this is still not bad

so this is "difficult" relative to like, maybe an intro class in combinatorics

in the grand scheme of things its still quite easy

[valid thicket]

😭 how do I get good at counting like you

[hidden totem]

well firstly

i can give general pointers

about mentality and habits

ive thought very deeply about how to teach combi for a long time

other than that its just practice

also i can link you something that might help, let me know if you want it and ill dm

[valid thicket]

yes please

[midnight crystal]

can anyone tutor me in discrete mathanatics im first year computer science student and i dont understand anything in discrete math. i got a midterm coming up and i am not prepared for that

[tall comet]

I don't think someone will personally tutor you but of course feel free to ask questions and people will answer

[true venture]

Would AABC and AADE be considered two patterns here?

[cedar sentinel]

Is this a good place to ask Theoyr of Computation Questions

[agile magnet]

for an introductory course yea this channel is probably fine

[cedar sentinel]

Thank you

[spring hound]

Yes.

With strings, the order matters, so "BACA" and "DAEA" are also separate valid strings.

[true venture]

Gotcha, they said patterns which I guess could mean 2 of the same letter followed by 2 different letters, both strings would be that pattern

Guess to find the answer you could look at all unordered groupings of 4 letters then sum the permutations of those.

@spring hound how would you find the answer?

[spring hound]

You have to be careful because AABC has 24 permutations, but that allows A_1A_2BC and A_2A_1BC to count as two strings when it should only count as one.

[spring hound]

You can use stars and bars on this, I believe.

Hmm, never mind.

Need to think a bit.

[true venture]

For AABC the number of permutations is 4!/2! . Dividing by 2! Accounts for the two As

[spring hound]

Right.

I mean, the long way is to do:

4 As: 1
3 As: 5 * 4
2 As, 2 Bs: 4C2
2 As, 1 B: 4 * 4!/(2! 1! 1!)
2 As, 0 Bs: 4C2 * 4!/(2! 1! 1!)
etc

[true venture]

Yea, that's exactly what I was trying to describe earlier, maybe there is a more concise way

[timid tartan]

Buddy I code in prod

[lusty ridge]

11 LETTER WORD WITH ALL DISTINCT LETTERS IS PRESENT with 5 vowel and 6 consonants

if a 3 letter word has to be formed from these letters what is the probability that a word with atleast 2 vowels is formed

[graceful shell]

can i put here analysis?

[stray reef]

analysis? like mathematical analysis? derivative/integral stuff?

that's better in #calculus or maybe #real-complex-analysis @graceful shell

[graceful shell]

no

limit value calculation

and things like that

[stray reef]

#calculus definitely.

[graceful shell]

i see

[fading jewel]

any help on this question? how to prove it.

[haughty garden]

Let A denote the matching produced with the girls proposing, and let A' denote the matching produced with the boys proposing. The forward direction is clear; if there is only one stable matching, then A = A'. For the backward direction, use the fact that the propose and reject (Gale-Shapley) algorithm is optimal for the side that is proposing and is pessimal for the side rejecting

[coral berry]

Hi peps. Can someone write this in set notation?

int[] A = [1, 2, 3, 4];
int[] B = [9, 8, 7, 6];

if (A.Length != B.Length) return;

int[] C = new int[A.Length];

for (int i = 0; i < A.Length) {
  C[i] = A[i] * B[i];
}

[brave rock]

No, this cannot be expressed via sets.

Sets have no inherent order to their elements.

You need n-tuples, or perhaps functions to describe this.

[coral berry]

I see.

[brave rock]

You can encode this in a reasonable way by letting A and B be functions A, B : {1, 2, 3, 4} -> N

So for example A(1) = 1, and B(1) = 9.

We don't tend to 0-index in maths.

Then you would define C(i) = A(i) x B(i) and you're done.

if (A.Length != B.Length) return;
This is redundant of course, because we statically know A and B are the same length anyway, so I'm ignoring it

[tawny agate]

How can we prove 1 + (nC2) + (nC4) ........ = n + (nC3) + (nC5) .......... (As in nCr = n!/r!(n-r)!) ?

[hidden totem]

hint: what is the probability that if you flip n coins, the number of heads is even?

[hidden totem]

we tend not to, but especially as mathematians, we should, it should be the default when there isnt a clear advantage to indexing by something else

[brave rock]

I don't really think so. The most important thing is consistency.

[hidden totem]

i will concede that in communication, the most important thing is consistency

but i think indexing from 0 as the default is mathematically more natural, as that is how we define the numbers in set theory, and thus maintain regularity

also avoids off by one issues with computing cardinality

thats why thats the standard in programming today, for good reason

[haughty ferry]

I saw this graphic and came up with this math problem:
For which (a,b,m,n) s.t. a≥b ∈ ℝ, m≥n ∈ ℕ is the following possible: There is an mxn grid of axb rectangles, There are m*n non-intersecting unit-diameter circles whose tangency forms a connected graph, There is a bijective mapping between circles and rectangles such that each circle intersects the rectangle it maps to

Several trivial cases:

• If b = 1 and n ≤ 1, possible (oops, I thought about it harder and not always)
• If b = 2 and n ≤ 2, possible
• If n = m = 1, possible

[azure smelt]

Suppose there are 6 questions in an exam paper , find the number of
ways in which a student can attempt one or more questions.

Can someone pls solve this?

[dreamy coral]

You can either try a problem or not try

So let's count the total possible ways you can try

It should be 2^6 = 64

But we want to eliminate the one case where we don't try a single problem

So the answer is 63

[marble gust]

have you studied the pascal triangle

[heavy bronze]

anyone? https://discord.com/channels/268882317391429632/1343146151691423744

[lethal linden]

Yes

[oblique pelican]

In 5 minutes, hope you studied

[slim wagon]

For path graphs of odd length, adding redundant vertices does not change the spectrum of the graph(there are no new eigenvalues introduced, only the multiplicities of older ones are increased). But when I do the same for 4k cycles, things seem to change (d is the diameter of the graph and t is the number of distinct eigenvalues). Could someone explain why it seems to happen for odd length paths but not 4k cycles? (I chose these two graphs as they have 0 as an eigenvalue, and I assumed that adding 'redundant' vertices only increases the multiplicity of 0)

[cursive nymph]

why is the number of combinations WITH repetitions not equal to n^k/k!??

i'm clearly missing something..

[stray reef]

i mean, n^k/k! is not an integer most of the time for one

and also if you're trying to de-order permutations w/ repetitions, not all of them correspond to the same number

e.g. {a,a,b,c,d} gives less rearrangements than {a,b,c,d,e}

[cursive nymph]

oh, I see; thanks!

[quick tusk]

are these two statements equivalent?
"not every lecturer teaches a course"
"some lecturers teach at least one course"

[vestal bronze]

no

[quick tusk]

yeah i was thinking the same. But one of my hw questions had an answer that implied yes. Does this working out make sense to show that it is not equivalent

[vestal bronze]

no

you can read it and see the differnce

oh

yeah

not equivalent sure

[quick tusk]

how would i show it through this logicc representation. Im not good at arguing logic just by reading it rip

[quick tusk]

can u tell me the difference. Like it looks like "not every lecturer teaches a course" = "some lecturer does not teach a course". Does that kind of mean some lecturer does not teach a course and some lecturer do teach a course. Or i can't make that conclusion

[vestal bronze]

you can't

"some" means "not none" but doesn;t mean "not all"

that's the idea idk

[quick tusk]

yeah that makes sense

thank you

i think my hw answer sheet is wrong then lol

[tawny agate]

for the Pigeonhole Principle i have this problem where i understand the concept of the theory but i dont know how exactly do i appley it a question , i just wanna figure out how do i approach to find the proof , and what exactly i need to look for when i finish understanding the question , any suggestions ? i also need to mention once i look for the solution for a specific question i understand it immediately and i already tried to solve many question and almost 10 percent i sort off get it right

[agile magnet]

it would be helpful if you could state a problem where you're stuck

and what you've tried

then it'll be easier to help you hone what you know into something where you can more easily solve problems

[tawny agate]

alright one sec

Prove that in the sequence 7777, 777, 77, 7, there is a number that is divisible by 2003.

+-----------=

for this one i have no idea on how to start thinking to solve it

[hidden totem]

this is pidgeonhole principle?

[tawny agate]

yea am positive , its from my homework

[agile magnet]

Hm ok yea this is tricky

So if you have no idea how to start, here's a hint

The idea is to consider members of the sequence {7, 77, 777, ...} modulo 2003

This is because being divisible by 2003 is the same thing as being equivalent to 0 mod 2003

And now since we're working modulo 2003, there are only finitely many remainders to deal with, so we can apply pigeonhole principle

So consider the first 2004 terms in the sequence, so all the way up to 2004 7's

taking it all modulo 2003, can you prove first why there must be two terms of the sequence, say one term with m 7's and another term with n 7's where m < n, such that their remainders modulo 2003 must be the same?

(ping me when you answer)

[hidden totem]

this seems like a very roundabout way to solve the problem, i found a direct proof

(not your fault, they want you to use pidgeonhole principle, I'm simply pointing out that it's a weird choice of problem)

[tawny agate]

ur saying u can prove it without pidgeonhole principle?

[hidden totem]

yes

||since 2003 is prime, by fermat's little theorem, 10^2002 = 1 mod 2003||

||so (10^2002-1) is divisible by 2003||

||7*(10^2002-1)/9 is therefore also 0 mod 2003. multiplying by 7 doesnt change anything, and you can obviously factor out a 9, but since gcd(2003,9) = 1, this is safe to do||

||so a string of 2002 7's is a multiple of 2003, done||

verified explicitly with wolframalpha: ||https://www.wolframalpha.com/input?i=7(10^2002-1)%2F9+%2F2003||

[tawny agate]

i will try to proof it using pidgeonhole principle first i feel like am close , then i will check out urs cozmo

[tawny agate]

is it because terms of the sequence 7's mod 2003 there exist 2003 reminders , and because we have a sequence 7 that's goes to infinity , that means there has to be a sequence of 7's (i think the 2004'th sequence will have the same reminder ("if that make sense")?

@agile magnet

[agile magnet]

Well you don't know if it'll be the 2004th member that is the repeated remainder

But yes that's basically it, you have 2004 elements but only 2003 possible reminders so there must be a pair of elements in the sequence with the same remainder

Ok so say our pair is m 7s and n 7s where m < n

Call the two numbers x and y, so x < y

What is the remainder of y - x modulo 2003?

[tawny agate]

0 ?

2003

not 0

fuck

wait

yes y - x = 2003 and the reminder is 0 ? no

@agile magnet

@agile magnet thanks btw

@hidden totem we didnt learn fermat's little theorem so i dont belive i am allowed to use it on my exam , am pass on it thanks tho

[agile magnet]

Well you don't know that the difference is 2003

You just know that the difference is a multiple of 2003

But also y - x is equal to n - m 7s followed by a bunch of 0s right?

So then use the fact that gcd(10, 2003) to show that the number with n - m 7s, an element of your original sequence, is divisible by 2003

[tawny agate]

yea for sure thanks

[spring thunder]

@tawny agate

[tawny agate]

ouh wow i like the idea

[agile magnet]

yea this is what I was saying

in hindsight I should have written it out with more detail (and probably handwritten to be able to have more flexibility in what I can write)

[heavy bronze]

no

[odd sequoia]

i need to prove that amount of elements for every element inside pascal triangle is finite.

1. it is obvious that elements are distinct in 2 strings (one under another).
2. every string is in a form of the binomial distribution, so no sequence inside a string is infinite.
   are these facts strong enough to start proving the statement?

[stray reef]

what do you mean by "the amount of elements for every element"?

[odd sequoia]

i mean, every element is stated to occur a finite amount of times.

[stray reef]

except 1, right?

[odd sequoia]

yes

[stray reef]

aside from the 1's at the edges, the entries in the n'th row are each at least n.

[weary tiger]

I don't understand 2 things

1. Shouldn't ∅ = {u : u ≠ u} be {∅} instead of ∅ because we take the set of the set with no elements?
2. Is it true by extensionality that ∅ ≠ ∅ since there doesnt exist a set ∈ ∅?

[hidden totem]

1. no, because the empty set equals the empty set

so the empty set cant be a u, an element of this set

the empty set violates the condition u /= u

2. no, the empty set does equal itself

because it says for all, so it is vacuously true that each element satisfies the condition

there are several ways to think about why we define vacuous statements to be true in this way

firstly, think about it from a high level. when we say that 'every element works' we also intuitively should also have the equivalent statement 'you cant find an element that doesnt work'

this allow us to apply negation rules to our quantifiers. to negate an "exists", show that every candidate fails. to negate a "for all", show that one candidate fails

secondly, if we didnt vacuously assume truth, this would be very odd because it means that there exists a set not equal to itself, and it happens to be the empty set, the set at the foundation of every set, a weird exception you have to encode into your model to do anything

and thirdly, we assume in classical logic that vacuous statements should always by default by true

we make an argument by stating true statement after true statement to derive our conclusion

if even a single false statement is introduced, it poisons the entire proof because by principle of explosion we can now prove anything

any proof can introduce vacuous statements without impacting the validity of the proof

so they must be true, or else all proofs can be poisoned

[granite panther]

can the basic set algebraic formulas be used together with cortesian products? for example, can I factor out xC from ((A\B)xC)U((B\A)xC) so it becomes (( A\B ) U ( B\A ) x C?

apologies for the lack of use of LaTeX, havent learned to use it on DC and i needed a quick question

[valid thicket]

principle of explosion?

[granite panther]

are you saying that to me?

[valid thicket]

to @hidden totem

I've never heard of that

[hidden totem]

definition of cartesian product:

$$A \times B = {(x,y):\forall x (x\in A) \land \forall y (y \in B) }$$

so

$$(A \times C) \cup (B \times C)

= {(x,y):\forall x (x\in A) \land \forall y (y \in C) } \cup {(x,y):\forall x (x\in B) \land \forall y (y \in C) }

= {(x,y):\forall x (x\in A \lor x \in B) \land \forall y (y \in C) }

= {(x,y):\forall x (x\in A\cup B) \land \forall y (y \in C) } = (A \cup B) \times C$$

[vital dew]

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

[hidden totem]

so yes

[granite panther]

im a bit new to all of these new quantifiers/symbols, what does the upside-down V mean?

and the regular V?

[hidden totem]

oh V is "or" and upside down is "and"

logic symbol

[granite panther]

got it, thank you

[hidden totem]

if thats too technical just know that yes it is the same

[granite panther]

those are usually used when describing elements that belong to sets, right? and the usualy U and upside down U are used when describing relationships between sets? (i may be mixing up the terms since set relations are also something else)

[hidden totem]

yeh

U is union, and upside down is intersection

youll see an analogy between union/or and intersect/and

A union B = {x such that x is in A OR x is in B}
A intersect B = {x such that x is in A AND x is in B}

thats why their symbols are analogous

[granite panther]

thank you very much

my lecturer doesn't explain these things well

what could be some good internet resources for relations between sets (the thing where a greek-looking p is used) and also set 'representations' (where functions are graphed and stuff)? my lecturer listed all of the theory but i have no clue how, for example, reflexive, symmetric, transitive relations are utilized when doing actual exercises

i may be mixing the terminology since the terms are different in my native tongue

[hidden totem]

principle of explosion says that if you assume a false statement to be true, you can then use it to prove any statement true. in other words, all statements become simultaneously true and false

proof:

assume A and -A (this is the false statement that "poisons" the proof)

A is true (P and Q = T means P must be T)
-A is true (same reason)

A or B (T because one of these is true, specifically A)
since A or B = T, and A = F and therefore B must be true

we have now proved that any arbitrary statement B is true

[vapid chasm]

I got an exam tomorrow and I completely zoned out when we got to set theory bc it was too boring

am I cooked

[hidden totem]

ill give an abstract example:

the definition of transitive is:
if xRy and yRz, then xRz

so its useful in that knowing both of the preconditions automatically gives you the postcondition

the property describes the structural connections of the relation

so for instance, lets say you're talking about divisibility. if you can prove "x divides y" as xRy is transitive, then you can show that x divides y and y divides z implies x divides z

the divides example feels not so impressive because its already a fairly obvious example, but plenty of less obvious examples exist, and proving these properties in the general case makes it easier to work with the specifics

as for resources, someone else will have to chime in

[vapid chasm]

I remember there being a really large hotel and a barber in discrete math from lecture

or something

[granite panther]

so is a relation often some sort of mathematical expression? xRy means that x = some sort of mathematical expression involving y?

[hidden totem]

not necessarily

in school you tend to think of functions and relations as having simple to describe rules

but in set theory we treat them in the most general case

for example

lets take the relation =

we treat that relation as a set of pairs

because 3=3, we can say that (3,3) is in the relation

in other words, 3R3 can be thought of as (3,3) is an element of R

so if you compile ALL of these possible pairs (in this case there are an infinite number of them)

you might get something that looks like:
R = { (0,0), (1,1), (2,2), ...}

so this means that you could have very well behaved nice relations like the equals relation example we just gave

but we can also have arbitrary relations like:

R = { (3,9), (104, sqrt3), (pi, {3,6,7}) }

for some reason, for this particular relation R, we say that 3 and 9 are related, 104 and sqrt3 are related, but 5 and 5 are not related

completely totally arbitrary, but it doesn't matter, because as long as you have a set of ordered pairs, it can count as a relation

this isnt describable as any kind of formula except by explicitly giving the relation itself

[granite panther]

hmmm, i guess i somewhat get it

i guess im just used to having specific examples

and this seems like a complete and total generalization, so i have trouble grasping how it would work in specific examples

[hidden totem]

well yeah, the point of a lot of math is to generalize in order to make stronger logical statements

so you're gonna have to find a way to get used to that kind of thinking

did my example help though?

you can always construct your own examples when studying anything

like try to make some relations that are transitive and see what they look like

[granite panther]

i guess so, i mean, best way to see if i understand it would be by doing exercises

but the problem is that we have barely done any exercises in our lectures

[hidden totem]

sometimes writing out the full thing is also annoying so

alternate representations can also be highly useful

[granite panther]

mostly just theory and minimally proving the characteristics (reflexiveness, symmetry, transitivity, etc)

[hidden totem]

for example, suppose you have the relation
{(1,3), (2,3), (3,3)}

notice the domain and range together is just the set {1,2,3}

so draw those three numbers anywhere on the paper

and then draw curved lines connecting the pairs

so that anything connected is in the relation

this is another way to help you see structures that you might not be able to just purely writing out the relation explicitly

try to think about different ways you can visualize simple examples

wrestle and play with the ideas

that will help when you do get to the exercises, you will have built up intuition

for example, youre probably about to learn what an equivalence relation is

if you dont get a good feel for what these properties mean, it might be confusing as to why its even called an equivalence relation

[granite panther]

unfortunately we learned about equivalence relations in the same lecture we learned about relations in

[granite panther]

i guess the biggest problem is that we haven't really worked with exercises

well we did 2 exercises, but that wasn't really enough and we went straight into it

without really understanding how our thought process and solution must be written

i'm currently doing a test exercise (tried translating it best I could):
The set of all triangles is given in a relation xay (a is meant as alpha but i dont think that really matters), and x is similar to y. (there are also arrows pointed both ways between xay and x is similar to y)
and from this information i have to deduce whether the relation is
reflexive
equivalence
symmetric
transitive
inclusive
and my thought process is a such
if reflexive means that for any element a in A exists a relation aRa, then in this specific case it means xax and i think it's true, since two equal triangles are similar to one another.
it is symmetric because x is similar to y and thus y is similar to x (axy <-> yxa)
it is transitive because if a triangle x is similar to triangle y, and triangle y is similar to triangle z, then triangle x is similar to z (because they all share the coefficients in practice)
since these 3 are true, it is equivalence
and i guess it's inclusive becaues it's symmetric? not sure about this

this is what it looks like (''ir līdzīgs'' = is similar to)

[hidden totem]

perfect

you got it

[granite panther]

oh, so is it inclusive?

[hidden totem]

oh no idea what inclusive here means

but everything else seems right

[granite panther]

honestly i can't differentiate what it means from my formula sheet

also, the right hand side of the arrows usually explains the relation?

in this case the relation is that x is similar to y? (x~y)

and if it were xay <-> y = 1 + cosx
then the relation is the math expression?

[weary tiger]

Regularity: ∀x[ x≠∅ → ∃y(y∈x ∧ ∀z(z∈x → ¬(z∈y)))]
Wouldnt y := {z} and x := {y} contradict the axiom?

[fossil mural]

"if z is in x, then z is not in y" is true, because z isn't in x

[hidden totem]

bingo

[weary tiger]

what if you let z be the empty set?

[fossil mural]

well then z still isn't in x

[granite panther]

thank you very much for the help so far

[weary tiger]

z = {} y = {{}} and x = {{{}}}
wouldnt z be in y & x and y be in x?

[fossil mural]

no

x = {y} means y is the only element of x

the set that contains both y and z would be written as {y, z}, so {{{}}, {}}

[weary tiger]

I see
thx for correcting me

[granite panther]

now I have this exercise:
The set of all planes is given in the relations: xay <-> line x || line y, xby <-> line x is perpendicular to line y. What does the relation x(a'Ub)y mean? (a' is meant as the the inverse set)

1. empty set
2. line x is perpendicular to y
3. line x crosses line y
4. line x isn't perpendicular to y
   my logic is that a' means that x is not parallel to y, by extensions that includes line x being perpendicular to line y, and since not being parallel means that at some point the lines intersect (so does being perpendicular), then i deduce that the answer is 3. line x crosses line y

[hidden totem]

i havent seen this notation before so id be missing context here

but im sure once you know precisely what that notation refers to, youll figure it out

[granite panther]

i think my reasoning sounds fine to me

thank you

[muted basin]

is n! >= 2^(n-1) provable by idnuction for all natural numbers?

i cant figure this out

[cursive nymph]

this might be basic..

imagine we have 3 bins and 5 distinct balls. how many possible ways are there to put em in the bins, such that no bin is empty?

ok, we most probably do it in two ways:

• calc the total numb of ways there are to put 5 balls in 3 bins
• subtract the number of combinations when 1 or 2 bins are empty from that

I can calculate the second one, but I'm a bit stuck on the first part..

[muted basin]

ive gotten as far as the induction step where i multiply both sides by (n+1) to get (n+1)!

but (n+1)*2^n-1 makes no sense to me on how to manipulate

[little prism]

hint: ||2^n = 2*2^(n-1)||

[cursive nymph]

i was going to suggest doing something similar to the proof of lim 2^n/n! = 0

[little prism]

thats the same proof basically

[muted basin]

this is true but what after?

there is no way for me to determine this is greater than or less than (n+1)*2^n-1

all natural numbers includes 0 according to prof

i could divide 2^n-1 if i introduce your hint but

n+1 can’t be greater than 2

0+1 gives false

[hidden totem]

well, you can arbitrary restrict the induction step for a restricted domain

[muted basin]

idk how to use this for thus

weve just done induction

nothing with limits

[muted basin]

?

but we need to prove it for all natural numbers

[hidden totem]

ok look

[muted basin]

thats what the problem states

[hidden totem]

let P(n) be the statement "n! >= 2^(n-1)"

you can easily show that P(0), P(1), and P(2) are all true by directly plugging in and solving

[muted basin]

right, thats the inductive hypothesis

[hidden totem]

so you have a couple extra base cases, no big deal

[little prism]

you have 2*2^(n-1) and (n+1)*2^(n-1). yes it is possible to determine which is bigger

[hidden totem]

then for the induction step, just arbitrarily say it's for n>=2

[muted basin]

what

[hidden totem]

if P(n) then P(n+1)

[muted basin]

i need to prove it for ALL natural numbers

like its a part of the questiob

[hidden totem]

are you replying to me

[muted basin]

yeah

[hidden totem]

yes it still works for all natural numbers

you already showed P(0), P(1), and P(2) work

so your induction step

which is trying to show that P(n) for n = 3 and beyond work

you don't care that the induction step can fail for n=0 or n=1

because your base cases already cover it

[muted basin]

i’m going to attribute this to my professor failing us because we haven’t ever done anything that said we could do that

[hidden totem]

so you just say arbitrarily that your induction step only applies for n>=2

[muted basin]

now i know i suppose

[hidden totem]

like think about it this way

[little prism]

you dont need to exclude n=1. it still works for n=1

[hidden totem]

hold on lemme draw you a picture

yeah i just wanted to point out you can do a few extra base cases

i didn't do the nitty gritty in my head but i figured basing up to n=2 was safe

[little prism]

nitty gritty
n+1 >= 2

[hidden totem]

ok see this

the black is your base case

it's true, cool

the way you extend this to all natural numbers is by forming a rule that allows you to walk up the chain

P(0) gives you P(1), P(1) gives you P(2)

etc

more simply, if you ignore the P stuff:

is there any reason you can't do this?

[hidden totem]

this is actually not that trivial, you have distinguishable balls and indistinguishable buckets

[muted basin]

now that im seeing it, it makes sense

i just had the idea ingrained that we had to religiously follow the problem statement and didn’t know more than one base case was acceptable

welp

this was for a one question quiz 😭😭

he does credit for work so oh well ill get at least a 60 i suppose

[hidden totem]

yeah just remember that

induction in general can be very very abstracted

you can have all kinds of base cases and chains

as long as you eventually cover all the integers you need, it'll work

for instance, another way to do induction is to prove P(n) for all primes n

then prove that if P(n), then P(pn), where p is a prime number

then prove the missing finite base cases like P(0) and P(1)

because all of the positive integers can be prime factorized, so you can follow the chain back down to one of your base cases

[hidden totem]

https://en.wikipedia.org/wiki/Twelvefold_way#case_sx
this is one of the cases of the twelvefold way, using stirling numbers of the second kind

for small inputs, you can just do the dirty casework by hand in a number of different ways

but once the inputs get bigger, it's recommended you use the recursive relationships to compute the values

if you haven't learned it yet, don't worry, the reason it hasn't been taught is because it's not simple, just work out the dirty counting casework by hand

[cursive nymph]

thanks!

[iron bloom]

How is the sequence of complements decreasing?

The sequence En is decreasing so the complements should be increasing

Am I missing something

[little prism]

typo

[azure smelt]

Can someone pls solve Q1(b, c and e ) part.

My answer to a part was as follow:
x^2+x=0
x(x+1)=0
x=0 and x=-1

For ii)
1,4,7,10 since they are less than 12 and x mod 3 gives the remainder as 1.

Is that correct?

[oblique pelican]

looks right to me

for b you can use the inclusion exclusion formula

[stray reef]

for a you want to write them down as actual sets, ie {-1, 0} and {1, 4, 7, 10}

we won't solve the other parts for you tho

[azure smelt]

Alright thanks for checking

I get it. Im not cheating. Ive done my working but I dont think it looks right for part c and e?

This is what I did:
for b)using inclusion exclusion:
|AUB| = |A| + |B| - | ANB|
This means:
n+n-2= 2n-2
For ii) P(AUB)= 2^(2n-2)

For c) i know that first has to be true cause A-B N C means every element of A but not B

Hence we can say for left side: for every element belongs to a and c but not b

The same is true for right hand side

am i suppose to use set builder notation for this kind of question?

For part e)
i) false since if i took a value such as 1 it doesnt work
ii) this also doesnt work for 1
Why did i take 1 cause 1 is a positive integer

I think i got the reasoning right. I just need help with structuring

@oblique pelican

[turbid carbon]

Hi sorry this is probably a stupid question, but I thought Gn-Gn-1 would be the empty set? Since Gn is a subset of Gn-1?

[turbid carbon]

Wait never mind I just cant read

[cursive nymph]

can anyone recommend some problem-oriented resources for a first course in combinatorics?

starting for stars-and-bars

[graceful shell]

Gimme tips

For this discrete math

And analysis

[trim thicket]

i dont understand this at all
chatgpt is saying this is true
but i just dont understand how the summation expands into two and there's a big overlap between 0 to n and 1 to n+1
chatgpt says that the final summations actually add terms up to the same number as the previous one

i just realized that both orange stuff is exactly the same 😭

[trim thicket]

okay i got chatgpt to say this was all wrong by asking it more questions what the flip :explodes:

[hidden totem]

thats why chatgpt is unreliable for math

idk why everyone is using chatgpt

[brave rock]

ChatGPT is truly awful at math. Let this be a learning experience

[hidden totem]

you have YouTube and the internet

chatgpt decides probabilistically what character should come next in order to trick you into thinking it sounds human

this is what LLMs are

its honestly a miracle it can even do any of the math it can currently do

[arctic berry]

Im given $\neg t$, $s\implies t$ and $(\neg r \vee \neg f) \implies (s \wedge l)$ and I need to show the conclusion is $r$

[vital dew]

KySquared

[arctic berry]

Since a not(r) is there, i assume I will end this by invoking modus tollens, but apart from that im clueless

(No clue if that intuition is even right)

[cursive nymph]

u need to know that

• not [a or b] ≡ not a and not b (and similar for and)
• a => b is equivalent to not b => not a

assuming all reasonable assumptions

so flip ur implications and see what u get

[arctic berry]

Is it this?

https://media.discordapp.net/attachments/1254119568578973780/1345196439646765088/285594209963212800.png?ex=67c3ab4f&is=67c259cf&hm=4b631fe9fc44fcec7a9ecefefe48a022a23403caf2eed698886197f893e82bf1&

https://media.discordapp.net/attachments/1254119568578973780/1345197883946827846/285594209963212800.png?ex=67c3aca8&is=67c25b28&hm=f5b5b7b55e4f5df628eab8b5a4e47cd1c6b185701a4c2b14457259ccd04f5740&

https://media.discordapp.net/attachments/1254119568578973780/1345198439092453426/285594209963212800.png?ex=67c3ad2c&is=67c25bac&hm=b0e26dee8b66f7f27fe1581dc34219aa6b0ecd76e51bde9dbcb7263a7bde42c4&

https://media.discordapp.net/attachments/1254119568578973780/1345198785323597907/285594209963212800.png?ex=67c3ad7f&is=67c25bff&hm=e889be68ec951edf48cba32835856e868f0b3f11eadc88bd77c261fd5134358f&

https://media.discordapp.net/attachments/1254119568578973780/1345208116811141223/285594209963212800.png?ex=67c3b62f&is=67c264af&hm=1664c001c66ec29899ca9a1a907ba8e0c24acf911fd0cf40cdb3ec599aa83470&

So $\neg l \implies r$

[vital dew]

KySquared

[magic thicket]

Hi is my proof valid?

[vital dew]

Ledge

[weary tiger]

Can anyone give a hint-

[shy rampart]

does anyone have an idea on how to conclude C? Can't use rule for biconditional because it hasn't been discussed yet but here's my work so far

4. (A ^ B) v (-A ^ -B) // Material Equivalence from 1.
5. (A => B) ^ (-A => -B) // Material Equivalence from 1.
6. (-A ^ -B) => C // De Morgans Law from 3.
7. (A => B) => C // Exportation from 2
8. (A => B) // Simplification from 5
9. -A v B // Material Implication from 8

[haughty garden]

Consider a graph on 10 vertices, where you have a K_3 graph with 7 isolated vertices. Any edge xy in the K_3 graph must have that deg x = deg y = 2 + 2 = 4 and 10 >= 4. But the edge xy is not a bridge edge since K_3 - {xy} won't be disconnected

[quick folio]

either A and B are both true, or neither are true.
so here's the loose idea:
if both are false, then (3) implies that C is true
if both are true, then (2) implies that C is true

[shy rampart]

so pretty much the biconditional thing amiryt

or can I work around it using other rules

[quick folio]

no, you need the biconditional for C to be true

so, you can express the biconditional how you want but you need it

[shy rampart]

oh wait

is this valid nvm I got exportation wrong
(A=>B) =>C // Exportation 2.

(A => B) ^ (-A => -B) // material equivalence of the biconditional

(A=>B) // Simplification

C // Modus Ponens

[quick folio]

if you're allowed to just invoke the second line without proof, sure

[shy rampart]

ohh okay

I think Iget it now

thanks

[shy rampart]

wait so i need to prove (A ^ B) or (-A ^ -B)

[quick folio]

well it's just equivalent to the biconditional

[shy rampart]

ya but aaaaaaaaa

[quick folio]

but you don't have to

as long as you find a valid approach

again its up to you

[shy rampart]

yeahh but im stuck

prof insists to find other way instead of directing to the bicondiitonal

[azure smelt]

Find the maximum number of comparisons to be made to find any record in a binary search tree which holds 3000 records

Hey everyone. Im kinda confused with this question.

A sorting algorithm based on binary comparisons requires at least ⌈log2 n!⌉ comparisons.

The number of comparisons used by a sorting algorithm to sort n elements based on binary comparisons is Ω(n log n).

So, there must exist an item that requires at least ⌈log2(n + 1)⌉ comparisons to be added to the tree

[azure smelt]

I dont get which formula should I use for this?

I search on google and this is response I got:

In a binary search tree (BST), the maximum number of comparisons required to find a record is determined by the height of the tree. For a BST with n nodes, the height can be at most log2(n) in the best-case scenario (a balanced tree). Given 3000 records, the maximum number of comparisons would be log2(3000), which is approximately 11.55, rounded up to 12 comparisons in the worst case for an unbalanced tree.

[fading thicket]

hey

help me understand these

3.2 Least square method of curve fitting
3.2.1 Linear form and forms reducible to linear form
3.2.2 Quadratic form and forms reducible to quadratic form
3.2.3 Higher degree polynomials
3.3 Cubic spline interpolation
3.3.1 Equally spaced interval
3.3.2 Unequally spaced interval

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[twilit sundial]

no

unless you’re willing to put in the bare minimum effort to be specific on what you need help understanding

[oblique pelican]

Yeah that's like 10-20 textbook pages of info you're asking for

[deep tapir]

Anyone got an identity to help simplify this?

[azure smelt]

Can someone pls help me with this too?

[random oxide]

i have no idea how to approach this

[stray reef]

you will have to link us the video

[random oxide]

Thank u for this bc I carefully rewatchedand I found the part I missed abt solving it with the method 😭

Idk how i would justify it for a tho? Ig like they did in the picture he just said the summation of a from j=0 to n is a(n+1)

[stray reef]

a=1 in your case

[random oxide]

Yeah

Actually tysm ive been stuck on that for like

actually hours..

💀

[magic thicket]

Hi, this is a really dumb question but I dont get why this is a function? the answer says this is a function but shouldnt this be not a function because it fails the vertical line test?

[vestal bronze]

p/q is the input

you get p/q you write the q

there's always one

[cerulean wind]

the key point here is that p and q have no common factors

and that every rational can be written in a unique reduced form like this

[magic thicket]

wait so basically the x -> q means f(x) = q right? so instead of graphing x = p/q i just graph f(x) = q so its a horizontal line and since there is no common factors for p and q it can oinly be 1 value right?

[vestal bronze]

a horizontal line?

[neon harbor]

The q is not a constant, it depends on the x. It might be less confusing if you write f(p/q) = q

btw, this function can't be graphed in a reasonable way, so it's best to just forget about trying to visualize it

[magic thicket]

so basically for it to not be a function q needs to have multiple values, so since p and q have no common factors no matter what p/q equals the q only have 1 value so it cant have multple values so hence it is a function is this the idea?

[vestal bronze]

yes

[neon harbor]

Yeah, a function needs to have exactly one output for each input, and since p/q is a unique representation of a rational when p and q are coprime, this function is well-defined

[vestal bronze]

if p/q is 4, q =1
if p/q = 2/3, q=3

never ambiguous

[lethal linden]

Every rational number can be represented as p/q in exactly one way where p,q are integers with no common factors and q is positive ("reduced to lowest terms").

So, take a rational x, find the unique such p/q, and map it to q. That's a perfectly well-defined function.

[magic thicket]

Ok I get it now, this is a many to one function right? Since any integer input x results in 1 = q?

[lethal linden]

Correct, it's not injective.

Every integer is mapped to 1, for example, as you say.

[magic thicket]

K got it ty

[lethal linden]

And p/2 where p is an odd integer is mapped to 2 etc.

[lethal linden]

If you map p/q to 1/q instead of q you get something called Thomae's function and it has some interesting properties: https://en.wikipedia.org/wiki/Thomae's_function

It's periodic. It's continuous at every irrational number and discontinuous at every rational. It's nowhere differentiable. It's also Riemann integrable on any interval (the integral is 0).

[twin crescent]

HELP GUYS

IS ANYONE AWAKE

PLEASE

Does anyone know how to do B

Like I’m begging

[quick folio]

I mean since the problem doesn't ask you to give the simplest form

[twin crescent]

Hey

[quick folio]

you can just break down the shaded area to its smallest pieces