discrete-math

[errant bear]

remember though, this is with b =/=1

[weary tiger]

sorry not to sure what those symbols mean, b can't be 1?

[errant bear]

=/= means not equal, yes

if b=1, then a/b is an integer

[ebon valve]

can anyone help me with constructing spanning tree with depth first search and breath first search

[west zenith]

@humble bridge For your question about the laplacian you can just do the matrix product in the definition explicitely and find what is the term L_i,j

[stray reef]

do you still need help with this

[weary tiger]

hey sorry i forgot some of my basic math rationale

why wouldn't -(x)^2 be positive again?

sorry i meant

-(-x)^2

okay nvm excuse my dumb question

[ebon valve]

yep

the question is
Using alphabetical ordering, construct a spanning tree for this graph by using a depth-first search and breath-first search

what does it mean by alphabetical ordering

[stray reef]

the vertex names

they're named with letters of the English alphabet

they want you to order them as such

so that every time you have several options you pick the one that comes earliest alphabetically

[ebon valve]

This is my answer for breath first search

[stray reef]

.heic??

[ebon valve]

wait

[stray reef]

alright let's see

it looks like you started at J

[ebon valve]

ya

[stray reef]

one would have thought A would be the vertex to start at, given the whole

alphabetical ordering thing

also G would've been attached to F i think

[ebon valve]

i need to start with A ?

oh i think i need to start with A and end with K

Using alphabetical ordering, construct a spanning tree for this graph by using a depth-first search and breath-first search

anyone help ?

[errant bear]

...ann literally...

[last timber]

do you know what is depth-fist search and breadth-fist search?

[stray reef]

fuck sorry

i got distracted there

@ebon valve sorry for disappearing on you there

[stray reef]

yeah start with A but otherwise do the same thing you did

[ebon valve]

oh

wat is the difference between depth first search and breath first search

[last timber]

in depth-fist search you are adding vertices to the last one added as far as possible

and in breadth-fist search you expand each one

https://www.youtube.com/watch?v=NUgMa5coCoE&ab_channel=GerryJenkins

https://www.youtube.com/watch?v=x-VTfcmrLEQ&ab_channel=GerryJenkins

[stray reef]

in dfs you construct (or traverse) your tree down one branch as far as possible before hitting a dead end, then backtrack once you do so.

while in bfs you traverse all nodes at a given level before moving to the next level

[ebon valve]

oh

what u mean by backtrack

go back to the root ?

[ebon valve]

how do i solve this

im stuck at drawing the tree

[dire sphinx]

i did (a) of this exercise, but i am realizing that i don't quite understand what a corresponding relation means, e.g. in (b) and (e). can someone point me in the right direction?

is U = P(N) the universe of all sets of natural numbers? how do we interpret x+1 in (b)?

[naive gulch]

Can I just get general pointers of what they want me to do for this? I have a whole 5 premises and they want to have me pull up a set of conclusions from these 5? thats going to be a long inference

[stray reef]

maybe write them down symbolically?

like

H(x) = x is healthy, G(x) = x tastes good, E(x) = you eat x

1. ∀x: H(x) -> !G(x)
2. H(tofu)
3. ∀x: E(x) -> G(x)
4. !E(tofu)
5. !H(cheeseburgers)

4 is derivable from 1, 2 and 3 it looks like

[stray reef]

"gap" acts as a 7th color

[neat fog]

Is A(B+C) a product of sum form?

[humble bridge]

How would I prove this?

L_G is the Laplacian matrix of any graph G

[obtuse lance]

what's the sum of entries along a row?

[autumn pebble]

Am I going wrong somewhere, specifically I wanna make sure my induction hypothesis is correct so far

[humble bridge]

The sum of entries along a row?

Oh

The sum of a row in any Laplacian matrix is always 0

I know this now, but how do I prove that?

[weary tiger]

@humble bridge his point was

how can you use that to show 0 is an eigenvalue

[errant bear]

you forgot a term on the rhs of the inductive step @autumn pebble

[humble bridge]

I don't know how to use that to show that 0 is an eigenvalue

wait

it's [1 1 1... 1]^T

[obtuse lance]

😎

[humble bridge]

cause all the rows sum to 0! easy

ty

[obtuse lance]

you're welcome

[autumn pebble]

@errant bear what term?

[errant bear]

you have the sum to n = the sum to n+1

[autumn pebble]

Okay so sum of n+1 =sum of n (2k-5) + n(n-4)

@errant bear

[errant bear]

yea

[autumn pebble]

My induction hpothesis is correct right

[errant bear]

wait

no

[errant bear]

plus (n+1)((n+1)-4)

[autumn pebble]

Oh okay that makes sense

[humble bridge]

im kind of confused as to how i should go about doing this

the second picture is some context for the first

[blissful zenith]

can someone please help me prove the 1st and 3rd one? ive proben the secon and disproven the fourth

[weary tiger]

What does greater then sign with a slash through it mean?

[blissful zenith]

not greater than

[weary tiger]

thank you

[blissful zenith]

<@&286206848099549185>

[weary tiger]

https://cdn.discordapp.com/attachments/519982796970655767/805938018950316082/unknown.png

I think the answer is false and for the negation I got this - Can someone tell me if I'm doing it right?

[autumn pebble]

@errant bear Just to circle back I rewrote things in terms of L, I’m having some trouble with getting to my conclusion

[blissful zenith]

can i pls get some help w my questin

[weary tiger]

sry I would if I knew

[blissful zenith]

😦

[split shell]

I need help with this ANYONE

[frigid abyss]

why do they change the arrow symbol to the intersection sign when solving the negation. would it be wrong if it kept the arrow?

cant i just put (x>1 -> x/x^2+1 >= 1/3 )

[last timber]

because negation of a->b is a AND not b

[stray reef]

^

[worthy thistle]

Can I use master method to solve T(n) = T(n/2) + cN?

[blissful zenith]

can someone pls help me prove the 1st and 3rd one? i've figured out how to prove the 2nd and disprove the fourth

gcd is greatest common denominator

[blissful zenith]

<@&286206848099549185>

[vital dew]

Commander Vimes

[last timber]

(assuming a, b are both nonzero)

@blissful zenith use this

for first

[blissful zenith]

@last timber not gonna lie idek how that helps

[last timber]

a = xy, b = xz

then?

apply defn

[exotic shadow]

Hi! can someone pls help with these bijections??

[blissful zenith]

@last timber for the first one?

can i please get some heklp <@&286206848099549185>

just with the first one

for all naturals x,y,z gcd(xy,xz) = xgcd(y,z)

by contradiction io assume

idk how th to set this up

@last timber u there man

im struggling

[noble wasp]

can someone help me with this one

im nor sure if i did my proof right

[analog sonnet]

wrong channel

I can't really make much sense out of what's written there either

[frigid abyss]

for this problem could i use proof by contradiction to proove the claim x+y is rational is false by giving an example like pi+1/2. this would show the contradiction is false so the original statement is true

my book does it using proof by contrapositive. does either way work?

[deft cipher]

contradiction seems easier (without numerical values)

[sour arrow]

@frigid abyss
To be more specific, the contradiction is actually:
There exists an x, y ∈ R such that for rational x, irrational y, x + y is rational.

Note the "there exists". To prove your statement is false, it's not enough to provide a single example where it fails - you have to show that there's no example where it's true.

[dark bough]

This is the question and what i have so far can someone check my work

[noble wasp]

can someone explain this part in yellow

is there another way to say it?

[last timber]

without loss of generality you can assume that you do not have empty set in collection

[violet nebula]

@hazy pine

are u smart?

[hazy pine]

no

[violet nebula]

value of x

[solid garden]

what is a minset?

[halcyon oak]

this is clearly too advanced for discrete math

[short steeple]

graph theory question:
must a k-regular graph with odd vertices contain at least one odd cycle?

i'm kinda like completely stumped on this one lol

[weary tiger]

@short steeple

No odd cycles => bipartite, bipartite+k-regular => perfect matching => even number of vertices (contradiction)

[short steeple]

ok that’s awesome, i had already thought of something along those lines last night, but now i’m stuck on this: why does “no odd cycles” automatically mean “bipartite”

i saw the proof that bipartite iff no odd cycles but does that also mean no odd cycles iff bipartite?

sorry if that’s a stupid question, my defense is a) i just woke up and b) i don’t have any other defense lol

[weary tiger]

@short steeple iff literally means it is implied in both directions

so bipartite => no odd cycles but also no odd cycles => bipartite

[short steeple]

ok awesome thanks

yeah i see that now lol

[loud matrix]

Is this stating that A_1 has n_1 elements, A_2 has n_2 elements, etc.?

[near prawn]

yes

[autumn pebble]

Can someone help me out with these problems?

[weary tiger]

they are just gemoetric series

use the formula

[autumn pebble]

Okay but for f I can get a evaluation but g will have to be closed form correct

[weary tiger]

both will be closed form

[autumn pebble]

a sub 1 = 1-1/2

Or it’s just, a sub 1 = 1/2

And the ratio is *1/2

[fleet plinth]

Is this correct? and if it is can some explain it please?

[loud matrix]

Could somebody entail the difference between unique and discrete?

Say we got a 4 slot thing that includes two letters and two digits

How we would distinguish what is distinct and what is unique?

oh yeah

so if i have a 4 slot thing that must contain 2 digits and 2 letters, could you show me the difference between two distinct and two unique?

[shut fjord]

Can someone help verify my answer for algorithm B?

I highlighted the info I thought was relevant to algorithm B problem

N/3 is treated as O(n) time for worse case your shifting goes to n bits

That’s a given for me

So I got that algorithm b is 5(Tn/3) + O(n) which I think was a bit too easy..

*5 recursive multiplications

*splitting the binary expression into 3 parts (thus the n/3)

*doing n/3 shifting results in O(n) work

Can anyone come up with a counter argument to this?

[loud matrix]

I don't have the problem since I don't got the worksheet but it was something about this place having like a license where you have 26 characters and 10 digits and you needed to have unique 4 slot licenses that contained 2 characters and 2 digits and each license had a border - standard or premium. Changing either the id or border of the license plate results in a unique plate. It then asks how many unique plates could you have

[lethal prawn]

Can I get some help on a Problem?

1.4: Prove that A U B = A n B implies A = B.

n is supposed to be the intersection symbol.

[near prawn]

what have u tried

[lethal prawn]

I'm just confused on where to start.

I don't want to be cheap and look it up online, but it says that I should prove that A is a subset of B.

In order to prove that A = B.

[near prawn]

well that's one part yea

you also need to prove that B is a subset of A

so for the first part take a random element of A and try show it's also in B using the assumption

[lethal prawn]

I'll call that random element x for now.

[naive mural]

Not solving your assignment for you

[weary tiger]

I have a question, in propositional logic if you say P = Q does that mean if they have the same truth value it's true?

[errant bear]

[loud matrix]

if u had to compare the difficulty between proofs and combinatorics which one would you say is harder?

[pale epoch]

proofs are a part of every mathematical field

including combinatorics

[dull slate]

can anyone give me nugde on justifying the decreasing or the convergence of the $\sum_{k=1}^{n}{1/(n^2+k^2)}$ please:)

[vital dew]

4z1z

[naive gulch]

This is a really simple question, just wondering how n^2 is more than or equal to 0 follows in case(iii)

[near prawn]

n^2= n * n

and n<0

[naive gulch]

aah

that makes sense ty!

is integer n = 10a+b a known formula? Otherwise I have no idea what intuition would lead me to say that I'd express n through 10a+b

[balmy hornet]

Which of the following sentences is a proposition? (One or more could be correct)
A. Please fetch me that book.
B. How do you like your coffee?
C. Chicago is the biggest city in California.

I know that a proposition is a statement that is, by itself, either true or false.

For statement A. can there be define true or false? Like you dont know which book technically. right?

for B. Any answer can be true or false person, so that can be consider a proposition

For C. this would be completely false since Chicago is not located in California in the first place

[naive gulch]

B is subjective

So it can't be T/F

A is a request so I don't think thats T/F either

I'm still not sure how that relates though? the final digit is b I understand but I don't see how they connected 10 and a together so that a is the final digit/divided by 10

[dull slate]

any help?

[weary tiger]

compare to sum(1/k^2)

[balmy hornet]

Given two propositional variables, p and q. Assuming that p is True and q is False. Which of the following propositions are true? (One or more could be correct) ( Bold is my selected answer although correct me if my definitions are wrong)
A. p < - > q

• p implies q and q implies p
  B. p ∧ q
• p and q
  C. p ∨ q
• p or q
  D. p→q
• p implies q

When i am thinking that p is true then q cannot be true if it is stated as false. i was questioning of if that definition fits the statement so i do not know if my thinking is entirely correct

Yeah so how the question states that, "Assuming that p is True and q is False". My thought process is that us p is True then q cannot be true since it is stated as false. P cannot imply that q is true if q is false

i dont know if that makes sense to you though sorry if it doesnt

im trying to wrap this concept into my brain

yes, which was my 4th answer that p inplies q (p->q)

In this case, A is right?

ooooh okok (sorry i am also looking at truth ables in the presentation give to me) so this makes sense when written out. thank you!

[frigid abyss]

can someone help me out with this proof

ik i have to prove that y is a subset of z and z is a subset of y but idk how

[livid drum]

@frigid abyss
Here is a (heavily translated) proof of just the forwards containment.
Here is what it says.
Take any element x ∈ Y.
Then x ∈ X∪Y.
So x ∈ X∪Z.
Case 1. (x ∈ Z). Trivially x ∈ Z.
Case 2. (x ∈ X). Then x ∈ X∩Y. So x ∈ X∩Z. Thus x ∈ Z.
In either case, x ∈ Z.
fin.

[balmy hornet]

What is the negation of ∀x. (x>1→x/(x2 +1)<1/3)

• Definition: The negation of a proposition X is a proposition that is true whenever X is false and is false whenever X is true. This would mean the complete opposite (i.e. It is snowing outside. Negation: It is not snowing outside)

A. ∃x. (x>1→x/(x2 +1)<1/3)

• Same statement but only replaces ∀ to ∃
  B. ∃x. (x/(x2 +1)<1/3→x>1)
• this is the backwards version of the give statement but only replaces ∀ to ∃
  C. ∃x. (x≤1→x/(x2 +1)≤1/3)
• true because when x is an integer of 2 then 2/(2^2 +1) is 2/5. it is greater than 1/3
  D. ∃x. (x>1 ∧ x/(x2 +1)≥1/3)
• true for .5 is less than 1 and true for .5/1.25 is less than or equal to 1/3

Im confused on which is right. Is C or D right or and i misinterpreting A and B

[frigid abyss]

Thanks Pi, that was a clear proof. i understand it now.

[naive gulch]

ooh its like floor division so 31585454 turns into 31585450/10 = 31585454 effectively cutting off that last digit completely

ty

[tranquil jewel]

Is this good enough for this proof?

[weary tiger]

is it one to one?

(one to one means bijection right)

[tranquil jewel]

One to one is injective

Bijection is injective and surjective so it does include it

[weary tiger]

ye i was wrong just havent really heard it used much

but yeh your logic makes sense

essentially idea is just |A|=|f(A)|<=|B|

[tranquil jewel]

Ya I’m just not sure if I should prove it’s surjective thus a bijection, cause I am making assumptions

[foggy hatch]

Unfortunately, "a one-to-one correspondence" means "a bijection" even though in like every other phrase "one-to-one" just means injective.

[shut fjord]

Does anyone know or can throw me a hint as to how to do O(k) multiplications

Where x is just any real number you give the function, and y is an integer but it is y = 2^k

To return x = x^(y) or x = ^(2^k)

[haughty garden]

Injective: If f(a) = f(b), then a = b.
Surjective: Let f : A -> B; there is an element a in A such that f(a) = b for every b in B (in other words, the range is the codomain of the function).
Bijective: Injective and surjective together

[bronze rain]

The key idea is repeated squaring instead of just iteratively multiplying by x.

[patent galleon]

Hey I have a pretty simple conceptual question

is this saying that we plug in a number for x and then test with the resulting y

e.g. plug in 0 and get y = 0

which would then make this True

or is it saying plug in an x and a y and then evaluate it's truth

[bronze rain]

No , this says that there is some x such that no matter which y you plug in x=y^8

[patent galleon]

ok, so then it's clearly false, gotchya

[bronze rain]

Now try switching for all and exists and see if that is true

[valid wave]

hi question

so because that is true both ways

would A if and only if B

be true

in that case

[last timber]

@valid wave well

is statement if A then B true?

[valid wave]

yes !

[last timber]

and is if B then A true?

[bronze rain]

What ring are you working over?

[last timber]

it seems that concept of ring here is overkill

[valid wave]

yes thats true too

[last timber]

then by definition you have A iff B

[valid wave]

yay

ok

thanks

[last timber]

yw

[valid wave]

so just for clarification

A iff B is true when if A then B and if B then A are true

gotcha

thought it might be something weird with the logic

[halcyon oak]

mhm

pretty much

[naive gulch]

Just for clarification on this example, why does the third line suddenly have x = sqrt(2) ^ sqrt(2) instead of sqrt(2)

I don't quite the conlusion either. How does that prove anything?

[shut fjord]

Thanks! I’ll see what I can do with this info (:

[weary tiger]

Can someone please help ?!

[rich bramble]

[hint] ||Because of the Distributive property (A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)) and the Associative Property (A ∩ (B ∩ C) = (A ∩ B) ∩ C = A ∩ B ∩ C),
we can write
(B ∪ C) ∩ (B ∪ Cᶜ) ∪ (Bᶜ ∪ C) ∩ (Bᶜ ∪ Cᶜ)
as||
[step] ||(B ∪ (C ∩ Cᶜ)) ∩ (Bᶜ ∪ (C ∩ Cᶜ)).||
[hint] ||Because for A ∩ Aᶜ = ∅, this equals||
[step] ||(B ∪ (∅)) ∩ (Bᶜ ∪ (∅)).||
[hint] ||Because A ∪ ∅ = A, this equals||
[step] ||B ∩ Bᶜ.||
[hint] ||Because A ∩ Aᶜ = ∅, thus the answer is||
[answer] ||∅ ( empty set. )||

Please tell me if there is something wrong. I am not perfect.
Edit: This question has points so I spoilered each step.

[weary tiger]

Yeh makes sense

[valid wave]

Hi

im struggling to understand

when the floor of an integer

or a rational number rather

why the floor wouldnt like always be the rational number

like the floor of 5/3 would just be 5/3

[unreal stump]

Floor of 5/3 is 1

[valid wave]

whaaaa

oh the floor is the integer

i thought it would be like all reals or something

ok thanks

wait that actually gives me another question

[unreal stump]

Yes

[valid wave]

could you guide in me a direction of how i may prove something like this

i dont even see what like definition I would base this on

[unreal stump]

y=integer part (y)+ fractional part(y)

Floor(a+b)=a ,where a is an integer and b is a real number in [0,1)

[valid wave]

ohhh

wait so basically because x is an integer

the floor will always be that integer

so its only really the y thats changing things

🤯

is that the right way to think about it?

sorry for question spam

[unreal stump]

Kind of

[frigid abyss]

can someone verify if 52 is false and 64 is true

[merry steeple]

can anyone confirm that the highlighted part is an error?

should be just (H and M), and not (nonH and M) right?

[dull slate]

how is that helping? comparing so only inform us that the sum is majored by pi^2/6

[weary tiger]

@dull slate yeh which in turn justifies convergence

[dull slate]

i think we should also justify the increasing of it..

[weary tiger]

what are you actually trying to show converges lol

$a_n=\sum_{k=1}^n \frac{1}{k^2 +n^2}$

[vital dew]

same

[weary tiger]

are you trying to show that a_n is convergent?

(because it's bounded above by sum(1/k^2) and it's monotone increasing so has to be by monotone sequence theorem)

[obtuse lance]

I think we can do better with

$\sum_{k=1}^n \frac{1}{k^2 +n^2} < \sum_{k=1}^n \frac{1}{n^2} = \frac{n}{n^2} = \frac{1}{n}$

[vital dew]

Merosity

[weary tiger]

ye defo a nicer bound

[dull slate]

yeah right, thanks guys..

[naive gulch]

a rational number to the power of a rational # can never be irrational right

[errant bear]

2^(1/2)

[naive gulch]

yo

what

[errant bear]

is 2 rational

[naive gulch]

haha ik

my dumbass was wracking my brain for examples

smh my head

[errant bear]

a rational to an integer power, however

[naive gulch]

:D

(1/2) ^2

0 ≤ 𝜖 < 1.```

Am I tripping

Can't I just say n is an integer 1 and e = 0 and n = x?

[errant bear]

how can n = 1 and x

if x=/=1

[naive gulch]

I'm sort of confused what I'm being asked to prove

where does it say x = / = 1?

[errant bear]

im referencing this

you let n=1, then n=x

[naive gulch]

Like x = n + e and we say e is 0, then x = n?

[errant bear]

anyways, ots asking you to prove that every real number can be expressed as a whole number + some bit (decimal/fraction)

[naive gulch]

I think I'm misunderstanding the question

Oh

[haughty garden]

x is not necessarily an integer

[naive gulch]

I thought it was saying unique

[errant bear]

well, it is unique

[naive gulch]

Nevermind I was thinking we only had to show an example of one case

So it applies to all real numbers x I see that now based on the wording

So I can do proof by cases where real number x is an integer and not an integer?

[errant bear]

sure

oh yea, i shouldve specified that "some bit" could be 0, which then of course means x is an integer like you said

[naive gulch]

yeah thats what I originally was thinking about, I understand the frame of the problem now

if its an integer than e is 0 since there's no bits needed but if its not then e represents the right of the decimal

I think that would be sufficient proof for proof by cases

[errant bear]

ok well

this isnt like, formal so

you might want to make it more rigorous lol

[naive gulch]

Yeah I gave examples that satisfied the initial formula

thanks!

[errant bear]

oh um

if this is an assignment ur most likely not gonna get full (or possible even any credit)

[naive gulch]

Would this be sufficient?

[errant bear]

well, you dont mention n in your second case, besides the example which, although is good for you to get an idea of whats going on, is worth nothing in terms of the actual proof

"the numbers after the decimals" isn't really a rigorous argument, not trying to nitpick

[naive gulch]

Wait I said where 1 is integer n for my second case, wdym mention?

oh yeah I know that was kind of a muddy way of saying it

I wasn't sure how to phrase that

[errant bear]

the second case consists of everything excluding the example, so everything in the parentheses doesnt count basically

you only mention x and e

what is n?

[naive gulch]

ooh I see

n is still an integer though?

[errant bear]

yes

eg, let x = pi

[naive gulch]

then n = 3 and e be irrational number 0.14 and so on

[errant bear]

yes

also, you need to show uniqueness

which, isn't difficult, but is necessary

[naive gulch]

For a uniqueness proof I need to prove existence and then uniqueness right?

[errant bear]

yeah

[naive gulch]

Ah so this is kinda two parts

wack

[errant bear]

well, technically 4, if you have your 2 cases

[naive gulch]

Is this a little better than the muddiness I had before?

[errant bear]

yes, although

you need to explicitly say what n is in the second case

eg. floor(x)

[naive gulch]

restating that n is an integer?

I'm not sure what you mean by floor(x)

[errant bear]

no, what is n specifically

in relation to x

floor function basically rounds down the number to the nearest integer

you can think of this as chopping off the decimal

or, if for example x is rational, then x=p/q, in which floor(x) = a, where aq +r = p

i mean this is getting a bit out of intention from what the problem wants

[naive gulch]

Ooh floor division yeah okay I get what you mean

[errant bear]

this will allow you to "choose" a unique n, given x

[naive gulch]

Ah okay phew

This problem was more to it than I thought time to prove the uniqueness

[weary tiger]

does anyone know what that sign between the 3 and n^2 means

cant find it anywhere online

[faint narwhal]

Does not divide

[weary tiger]

oh i thought divide was something else. thx

[errant bear]

wtf

[novel beacon]

How are the renders of graphs on Wikipedia made?

[minor dagger]

What kind of graphs are you referring to?

https://csacademy.com/app/graph_editor/

I like this for making graphs

[novel beacon]

Using that program to make a graph with 120 vertices and 1200 edges would be rather tedious.

[faint narwhal]

2^n/n! is just 2/1 * 2/2 * ... * 2/(n-1) * 2/n

So if we multiply this by n^2 then one cancels with the last n

[faint narwhal]

Uh what

[nimble glade]

Hey guys! I have this problem for proving that I have no idea how to solve, help would be appreciated! the question: For all a, b E Z, if there exists cE Z so that ab= 4c+ 1, then there existsx y E Z so that a= 4x+ 1 and b= 4y+ 1. (E is element of...

[bleak jolt]

can i get some help with this question? pretty sure my answer is in the wrong format

[bronze rain]

I don't understand why the predicate is unary. Otherwise it looks ok.

[weary tiger]

can do that on matlab easily

im not sure which renders you're referring too though

[hardy quartz]

So i am stuck with this question cause I am struggling to figure out a formula to get the right answer on matlab

any help is appreciated

[stray reef]

you might start by writing the sum in sigma notation @hardy quartz

alternatively, you can add the terms two at a time, like this:

nterms = input("Enter term count to be used for approximation");

A = 0;
for i = 1:2:nterms
    A = A + 4/i - 4/(i+2);
end
disp(A)
disp(abs(A-pi))

[hardy quartz]

eh i have never seen that for i = 1:2:nterms

i usually do for i = 1:nterms

@stray reef

never got thought that method with for loops

[stray reef]

you can put any vector in a for loop and it'll iterate over the entries in the vector

it's super convenient

[hardy quartz]

the thing is I wonder if ill be allowed to use such a method

for me i was trying to do something like this

for i=1:n

    piValue = piValue + 4/(2*i-1);
    piValue = piValue - 4/(2*i-1);
end

And trying to figure out the "condition i should give it"

when to - and when to +

[stray reef]

I wonder if ill be allowed to use such a method
why not? it's valid matlab code and it has a for loop.

when to - and when to +
add when i is odd, subtract when i is even.

[vagrant elm]

Hello! Recently started brushing up on set notation and got this as part of an assignment.
I am unsure what is mean by "encoding a function" and "encoding a relation".
Can someone explain?

@weary tiger Yeah, each element in one set maps onto each element in another set

And so I assumed that the answer to b) is no since 484 is not part of R

Please correct me if I'm wrong

For the same reason, I think c) is yes, however I'm not sure since 17 now appears twice in R

[stray reef]

wonder what the difference is between encoding a relation vs being a relation

[vagrant elm]

The professor has a weird way with words, I'm pretty sure he just means if it is a relation

Why is b) yes?

and more importantly, why is c) no?

I haven't been given any, sorry

Not formally anyway

I found this online though:
A relation between two sets is a collection of ordered pairs containing one object from each set. If the object x is from the first set and the object y is from the second set, then the objects are said to be related if the ordered pair (x,y) is in the relation.

I understand the definition I gave is too vague

I was just pointed to a book but I could only find the definition of a binary relation

and last time I had anything about relations was 1.5 years ago

I see, my bad then

So if a relation is a collection of ordered pairs containing one object from each set, then why is b) yes if R does not contain a pair with 484?

Is it not a requirement that all elements be present?

So it is a relation because some objects from C map onto elements in D

However c) is no because then R would contain an element that is not a pair

Yeah that makes sense. Functions have one specific output for each element however relations may have multiple elements pointing to the same output in the range, correct?

Ohhh right, I see, so looking at the sets I sent, R is not a function because 17 outputs both y and z

Thank you, that was a good explanation, I get it now

Just unsure about d) now but a, b and c make total sense

One moment

OK I'd say yes to d) since (17, z) is now gone from R

and so there is only one output for each input

Also I have not heard of partial and total functions, but my intuition tells me that a total function maps all elements in the domain whereas partial is only some

Finally a term that makes total sense from its name lol

In this case it would be a partial function

Thank you for your help

[weary tiger]

2^|E|

each element can either be in a subset of not be in a subset

any ideas for this?

[stray reef]

what's G[A]?

[weary tiger]

oh mb forgot to define that

[stray reef]

ah ok

[weary tiger]

so just the subgraph induced by those vertices basically

[stray reef]

so essentially you need to prove that it's possible to paint the nodes of your graph red and blue such that each node is connected to evenly many nodes of its own color

[weary tiger]

like every problem seems to be induction pretty much but seems kind of useless here

yeh

[stray reef]

hmm

[weary tiger]

so i guess if its bipartite then thats easy enough

[stray reef]

give me some time to thonk about this

eh?

[weary tiger]

so i probs just need to work out how to do it for odd cycles?

[stray reef]

i dont immediately see how its trivial for bipartites

oh nvm

of course

[weary tiger]

also i realise

we only need to do it for connected graphs

[stray reef]

of course we do

[weary tiger]

because if it splits into components i can use induction

and if theres an element of order 0 or 1 i can also use induction

[stray reef]

you can paint each component separately

yeah

anyway a single odd cycle is easy cause you can just paint it one color

[weary tiger]

oh yeh ofc

[stray reef]

(meaning A = E and B = empty or the other way around in the original terms)

hmmmmm

[vagrant elm]

Using this formula to compute the cardinality of a power set equals 16 for a power set of a power set.
However, when I compute P(P(B)) I get a set with 32 elements instead of 16.
What's going on here?

I feel like I either misunderstood something or did something wrong, or maybe the point of the exercise is to prove that the formula does not work for power sets of power sets?

[weary tiger]

this isnt a subset

{{2},{empty,3}} isnt an element of P(B)

[vagrant elm]

hmm then i'm not sure how to find P(P(B))

[languid cradle]

having some trouble w this

[faint narwhal]

Have you seen the proof of the fact that in a planar graph, you have to have that e <= 3v - 6?

[languid cradle]

yep

d(f) >= 3 for any face

ohhhh

so maybe I just work that backwards

but with an equality

2 = V - E /3

[faint narwhal]

Okay another way to see it is to use the fact that v - e + f = 2 here

[languid cradle]

yeah

[shut fjord]

Still stuck on this problem

[languid cradle]

ok thanks I’ll try it and let u know

@faint narwhal

[faint narwhal]

@shut fjord what have you tried?

[shut fjord]

I tried using powers of 2

But when I go to something like

(3,2^3) or (3,8)

It doesn’t really help

Because I need to do at most 3 multiplications

[faint narwhal]

your power of 2 idea is on the right track

[shut fjord]

Can we express 27 as a power of 2?

It would be something annoying like.

2^4 + 11

2^4 + 2^3 + 2^1+2^0

[faint narwhal]

uh why do you need to do that?

[shut fjord]

Trying to avoid unnecessary multiplication

I think there’s a sub problem where if I can get to 27

I can get to 6561

Cause 6561 = 27 * 27 * 9

Or I can try getting to 9 first

[languid cradle]

ok got it beautiful

really pretty math

[faint narwhal]

I'm not sure why you're looking at those numbers

the power you're raising things to are always powers of 2

[languid cradle]

oh, wait, I just assume the degree of each face is the same?

I have 3 |F| = the sum of d(f)

but 3 |F| = |F| df only follows if df is the same for all f right

[faint narwhal]

yes that is true

[languid cradle]

😭

should I do like cases

if df is the same obv df = 3

[faint narwhal]

no I'm not really sure what you've done or are trying to do

[languid cradle]

here I’ll show u

ok so the last line doesn’t follow

but up until then it’s all good I think

[faint narwhal]

ok yeah

so you have in some sense that the "average" degree of a face is 3 right

[languid cradle]

yeah

exactly

[faint narwhal]

but what's the minimum possible degree of a face?

[languid cradle]

3

ohhhh

lol

so any one can’t be more than 3

cus then another would have to be less than 3

to maintain the average

[faint narwhal]

yep

[shut fjord]

I think I found the approach here

I have 2^3 3’s so I can split that in half every iteration

So my first iteration would involve 3^(2)

The second would involve 3^4 which is 3 * 3 * 3 * 3 or 9 * 9 which gives me 81

[faint narwhal]

Right

[shut fjord]

Something like this

[faint narwhal]

so all you need to do at each step is just to square the previous thing

[shut fjord]

Yeah

I understand it intuitively but

like the relation seems mysterious to me

Thank you

(:

[weary tiger]

discrete math is awesome

my fave topic

[naive gulch]

Its fun

until its not

{x ∈ R | x is an integer greater than 1}

For checking for subsets what would the difference be between 2 and {2} for this

2 is included the set because 2 is an integer greater than 1, but the set containing 2 would not be?

[last flicker]

the set containing 2 clearly can't be in a subset because its not in the original. The original contains only numbers, no sets.

[naive gulch]

ok yeah thats what I thought thanks!

For this that I wrote up, A ∈ B but A is not a subset of B right

[last flicker]

Other way around actually.

[naive gulch]

IF I changed it to 0 < x <_ 2, then A is a subset of B but A ∈ B?

oh

oh A would be {2} right

[last flicker]

Yes

No

[naive gulch]

ah gotcha

oh?

[last flicker]

{1}

[naive gulch]

sorry wait yeah thats what I meant

How could I make it both A ∈ B and a subset then?

[last flicker]

A clearly can't be in B because B doesn't contain any sets and A is a set. However it is a subset of B as every thing in A(i.e. just 1) is also in B

[naive gulch]

Yeah so A = {1} and B = {1, 3, 5, 7, 9} right?

[last flicker]

Correct

[naive gulch]

Ah okay

So because A is in a set, then A cannot in B. But wouldn't it only be a subset if B = {{1}, {3}, etc}}

[last flicker]

Well because A is a set it can't be in B. As for subset, i think you misunderstand what a subset is

A set Y is a subset of a set X is everything in Y is also in X

[naive gulch]

Ah okay

So {1} has just element 1, {1, 3, 5} has 1 inside it

therefore {1} is a subset of {1,3,5}

[last flicker]

True

[naive gulch]

But {1} is not a subset of {{1}, {2}}

[last flicker]

True

[naive gulch]

Because {1} contains element 1 and {{1},{2}} contains the elements set containing 1 and the element set containing 2

[last flicker]

More precisely, the second set doesnt contain 1

[naive gulch]

yeah sorry thats what I was trying to get across

the second set contains sets but not the element 1

So in that case, is there any way I could say both set A is an element of set B and a subset of B?

I can't think of a way to make it so that its an element and a subset

[last flicker]

If you had A={1}, and B={1,{1}}

Then A is both a subset and element of B

[naive gulch]

its a subset because element 1 inside set A is also inside set B, and an element because {{1}} inside B is an element right?

[last flicker]

Well {{1}} is not in B, but A={1} certainly is

Just to be clear, something being in a set is just another way of saying its an element of that set

[naive gulch]

sorry what I meant is I was representing it as a set not an element

Ok got it I think I understand then

○ Set A contains the element 5, so does set B therefore A is a subset of B
○ Set B contains the element which is the set {5}, and since set A is {5} therefore A is an element of B

[last flicker]

Uh so you're saying A={5} and B={{5}} or what

I'm not quite sure I understand the question

[naive gulch]

Sorry for confusing you!

20. Find two sets A and B such that A ∈ B and A ⊆ B

This is the question I'm trying to answer

where A is {5} and B is {5, {5}}

[last flicker]

Yes, that looks like a good answer.

Let me look up at your previous message now

[last flicker]

Sure, so the first dot point should prob specify that A contains only 5, and the second is fine save the fact that you could probably remove "the element which is" and get away with it a lot more concisely

[naive gulch]

Ah okay tysm!

[sand cipher]

need help with this, abit confuse with this section of the chapter

[sharp quarry]

i think the switched "Belong to" do not make sense

It might be a typo

[night mauve]

I was thinking that aswell

But 2 can be read as for any x that is an element of the real numbers if x^2 < 0 then 2x > 1

[sharp quarry]

Correct

[last timber]

second is vacuously true btw

[night mauve]

Ya

[sharp quarry]

It can be read as There exists an Integer n such that for each integer m, mn<1

[last timber]

and this is also true (but proof is left as an exercise to the grater)

[iron pine]

i did not understand how the degree of u can be zero

[iron pine]

<@&286206848099549185>

[stray reef]

@iron pine a vertex of degree zero is a vertex that is not connected to anything

[iron pine]

yeah so , in this grap is there always a vertex that is not connected

[stray reef]

the problem imposes no requirements on your graph besides having at least two vertices and no loops

so the answer is of course not

[iron pine]

so should i prove or disprove the statement

is it false or true

[stray reef]

what do you think

[iron pine]

i am not sure unfortunately

[stray reef]

reread or conversation

you: yeah so , in this grap is there always a vertex that is not connected
me: [...] so the answer is of course not

[iron pine]

sorry for asking but i am not good at understanding

precise answer would be appreciated

what i understand is statement is false and i should disprove it

right?

[stray reef]

yes, the statement is false

[iron pine]

so how can i disprove it

[stray reef]

give a counterexample

a graph with

• at least two vertices
• no loops
• no isolated vertices

[iron pine]

yeah there is counterexamples but does it prove anything

i should give solid answer

how can i prove scientifically

[stray reef]

"scientifically"? i beg your pardon?

if for whatever reason you are not satisfied with 1 counterexample as disprpof (even though in math a single counterexample is perfectly good for disproof on its own),

then i could present to you 2 counterexamples, or 10, or even infinitely many

[iron pine]

sorry if i offended, but how can we know maybe there is an example that conforms the definition of this graph. also, counterexample is not accepted in this question i should explain the reason

[stray reef]

wym by "counterexample is not accepted"

explaining why what you're presenting is a counterexample in the first place will be reason enough

"Let X be an object with such and such properties, then this and that statement is true"
this states that all objects with those properties make the statement true

if you find even one counterexample the statement is rendered false

statement: all geese are white
disproof: here is a goose that isn't white.

you didn't "offend" me either

seriously though, why do you say counterexamples are not accepted?

did your teacher say "if you present a counterexample as disproof your entire family will be sent to gulag"?

[iron pine]

so what should i write. there is bunch of counterexamples after drawing a graph that is counterexample i say this disproves the statement. this can not get point

[iron pine]

also the question does not say "all" it says there is at least one example

[stray reef]

"Let [...]. Then [...]" means all

draw a graph that's 5 vertices connected in a row, point at it and say "this doesn't have any isolated vertices nor vertices connected to everything"

how do you know this won't get a point

[iron pine]

does not Ǝ this symbol (reverse E) mean there is at least one example

[stray reef]

it refers to vertices not to the graph itself

seriously you are saying your teacher won't let you disprove "all geese are white" by presenting a black goose

[iron pine]

i just wanted to be sure. if you say draw a graph that is counterexample it works me and also sound logical for me. but i wanted to be sure that i give the correct solution

is it counterexample

can you send any counterexample

[stray reef]

of course???

your graph is directed though

you should have an undirected graph

just remove those arrows on the edges

[iron pine]

so just drawing this graph(without arch) an saying that "here is counter example. so this statement is false" is correct disprovement?

[stray reef]

of course??? disproof by counterexample is extremely common

[iron pine]

ok thanks a lot. i am really grateful for your time and explanations

[vital dew]

You already have the selfroles studying!, do you want to remove them? (y(es)/n(o))
(Tip: use ,iamnot to remove roles without this prompt.)

Session timed out waiting for user response.

Feb 7, 2021, 9:30 AM

[iron pine]

i have one more question, is there any graph as described in the question

is it possible

Let G = (V, E) be a simple undirected graph without loops, where |V | ≥ 2.
∃u∈V ∃v∈V such that δ(u)=0andδ(v)=|V|−1,where δ(v) is the degree of vertex v.

[stray reef]

no, there does not exist such a graph.

but the proof of that is actually more interesting than the counterexample thing we talked about 6 hours ago

i can tell it to you in two ways: the formal boring way or the fun memorable way

which one do you want

@iron pine

[iron pine]

the formal boring way

[jolly olive]

WHAT?!

To each her own, I guess ...

[iron pine]

the both would be perfect, but if i have 1 choice i would choose the formal boring way

[stray reef]

k fine

suppose there exist vertices u and v of degrees 0 and |V|-1 respectively

notice that this means u is adjacent to nothing while v is adjacent to all the other vertices in the graph

in this scenario, u and v must be adjacent (by definition of v) and not adjacent (by definition of u) at the same time.

contradiction.

[trail steppe]

nitpick: either specify u!=v, or 0!=|V|-1

[stray reef]

|V| ≥ 2 guarantees it

[trail steppe]

or that

[stray reef]

the fun memorable spin on this is as follows:
imagine the vertices represent people in a town, and the edges represent friendships.
call someone a hermit if they're friends with nobody, and a leader if they're friends with everybody.
the question becomes: can a town have both hermits and leaders?

of course not! consider what'd happen in a town that had both.
would the hermit and the leader be friends?

they must be friends or the leader wouldn't be a leader, but they can't be friends or the hermit wouldn't be a hermit

so a town with both a leader and a hermit cannot exist

[atomic forge]

Is it correct to say that since n logn < n^2 for all n > 0, that Θ(n logn) = O(n^2)

[stray reef]

if a function is Theta(n log(n)) it'll also be O(n^2) but not the other way around

[iron pine]

@stray reef thanks a lot. the both solutions are catchy and fully logical. i am grateful

[atomic forge]

how do you notate that

[stray reef]

you can write $\Theta(n \log(n)) \subseteq O(n^2)$ i guess

[vital dew]

Ann

[stray reef]

if you interpret each notation as referring to a class of functions

[atomic forge]

ok thanks

makes sense

[atomic forge]

Can you find a better bound than O(n^3) for an algorithm that finds whether any two elements in an array sum to any other element, so find whether there exist i, j, k where A[i] + A[j] = A[k]

[stray reef]

as in, design an algorithm that runs faster than O(n^3)?

what do we know about the elements of the array?

[glass condor]

You can find (if they exist) two elements that sum to a given value in O(n), so you can do at least as good as O(n^2).

[slow jewel]

Isnt this 5!

[unreal stump]

No

[slow jewel]

why is it 2^5

[unreal stump]

The subset can have either 0,1,2,3,4 or 5 elements

[weary tiger]

for every single element you can decide whether it is in a subset or not. So it is 22222

So for example you decide whether 1 is in the subset or not- thats two options

and when you do that decision for every single element in the set

you have 2^5 options

[slow jewel]

i see

my way of thinking is weird

[weary tiger]

what is your way of thinking

[slow jewel]

p(5,5)

[weary tiger]

why would you use permutations?

[slow jewel]

order matters

[weary tiger]

does the order really matter?

because a subset {1,2} is equal to {2,1}

[slow jewel]

ah fuck

so order doesnt matter, but what about repetition

[weary tiger]

there cant be repetition

because {1,1} is not a subset

i mean

it is

because {1,1}={1}

[vital dew]

Laffen

[weary tiger]

but those cases are all the same so you don't count them separately

[slow jewel]

ok

thank you brothers

[graceful vapor]

https://i.imgur.com/7m49cIh.png

What does it mean about number of strings of n zeros?

If it's easier to explain in voice chat let me know I am able to talk.

[coral raven]

length n?

idk

[shut fjord]

I was thinking...if we had a rod of length n

We could cut it by x pieces

Then we would have n - x length left over

And then we can make a recursive call over this n - x piece

Until we hit n = 1 or n = 0

It’s a dynamic programming problem so I’m a bit unsure how I would go about writing the recurrence relation for tihs

[graceful vapor]

https://i.imgur.com/7m49cIh.png

ok so I understand what it means by strings of n zeros and ones that contain an even number of ones

but when I try to turn that statement into something for p(n), logically I can get to 2^(n-1). but that's already given.

so I don't what to do in the induction step

[pale epoch]

you assume that it is true for a fixed n, so that there are 2^(n-1) such strings of length n and then you consider strings of length n+1

you can i.e. think about turning a string of length n into a string of length n+1 by appending a symbol

[graceful vapor]

How do you seperate (8^n - 3^n) from 8^(n+1) - 3^(n+1)?

I'm working on the next question and im stuck on this

https://i.imgur.com/kSTy66B.png

[minor dagger]

separate the exponents

[obtuse lance]

you can factor it as $5*\sum_{k=0}^{n-1} 8^{n-1-k} 3^k$

[vital dew]

Merosity

[obtuse lance]

@graceful vapor

[mystic moss]

or if you're doing it with induction, try adding them together

[mystic moss]

yeah your idea sounds good. you might try writing it as "max_{x \in [1 ... n]}" and then whatever you're maximizing over all x. notice that you don't really need a separate case for n = 1.

[clear sierra]

Can anyone help me get started on this? I'm having a hard time understanding the notation equal to A_i and B_i

[stray reef]

@clear sierra have you seen interval notation before?

[clear sierra]

I've seen interval notation before yes, it's the other bit to the right of the intervals

"x is a subset of all real numbers for -i < x < i"

like I don't know how to view that as a { } set

[stray reef]

$\in$ does not mean ``subset''

[vital dew]

Ann

[stray reef]

{x in R : -i < x < i} reads as "the set of all real numbers x such that -i<x<i"

[clear sierra]

Oh I got it confused with ⊆

Oooh and then it works like a summation

[vital dew]

Levi

[clear sierra]

Would This be right? @stray reef

[stray reef]

the intersection of A_i is just ∅ not {∅}

everything else is fine

[clear sierra]

okay thank you so much!!

[clear sierra]

what does this symbol mean

$\forall$

[vital dew]

Levi

[stray reef]

"for all"

[clear sierra]

im dumb

im dumb realized it's literally right there in the Tex

thank you

[void kraken]

can anyone please explain these two

I mean i initially thought it'd be like
C(X) = Contradiction

Therefore,
C(x) --> ~C(X)

but that isn't right ryt?

[glass condor]

a contradiction is
$$
A \land \lnot A
$$

[vital dew]

ConfusedReptile

[glass condor]

and the negation of that is $\lnot(A \land \lnot A) = \lnot A \lor A$, which is indeed a tautology

[vital dew]

ConfusedReptile

[autumn pebble]

?turor

?tutor

I am having some trouble understanding this problem, I cannot find something similar to it in my textbook

[pale epoch]

this is not a problem, its just a definition

[bronze rain]

Have you seen such recursive definitions before, orcacaca?

[autumn pebble]

I think I have, I know my answer should be a number

[bronze rain]

What do you mean by answer? A closed form for this?

[autumn pebble]

They don’t want an expression of T it should be a number, I just don’t understand how I can make a sequence of T(n)=1 with both of the other expression even and odd T

Oh

I’m supposed to evaluate T(7)

[bronze rain]

Hint: for every two steps you take starting from an odd number, the number decreases.

Well that will give you an idea of what it might look like generally also. In vague terms, since the recursion just goes to another number, you don't really get anything 'new'.

[autumn pebble]

So start with T(n) = 1 and apply the definitions in a sequence ?

[bronze rain]

No, start with what you want to compute. Since 7 is odd you would first use the rule for odd numbers.

Once you do it for 7, you may want to try some other numbers and see how that goes.

[inner lava]

Is there any precedent in graph theory for the idea of graphs where you have... what I can only call hyper edges?

you have nodes

edges that connect nodes

hyper edges that connect edges

[glass condor]

I have an idea where you encountered that idea 🙂

https://xkcd.com/2036/

xkcd: Edgelord

If you study graphs in which edges can link more than two nodes, you're more properly called a hyperedgelord.

[autumn pebble]

?tutor

Is there a formula to get the 451st term of this arithmetic sequence?

[glass condor]

is the sequence just "latest term + 9"?

[autumn pebble]

Yes

[glass condor]

if so, it's easy to figure out a formula for the series, and prove it via induction

[autumn pebble]

Is there a layout of the formula

How would I got about producing one

[glass condor]

You can easily guess that it's linear, and find the coefficients by fitting through the first two points.

like, $a_n = k n + b$ for some $k$ and $b$.

[vital dew]

ConfusedReptile

[autumn pebble]

Okay so a451 =4(9)^450+9

4 + (9)^450

+9

[glass condor]

what

[autumn pebble]

I’m trying to solve for the k

[glass condor]

you can do so by fitting the first two terms

like, zeroth and 1th

[autumn pebble]

What do you mean by fitting

[glass condor]

Require that $a_0$ is 4, as it is. So you know that $k * 0 + b = 4$

[vital dew]

ConfusedReptile

[glass condor]

require that $a_1 = 13$, as it is. So $k + b = 13$

[vital dew]

ConfusedReptile

[glass condor]

solve for $k, b$.

[vital dew]

ConfusedReptile

[autumn pebble]

So b wouldn’t be 9

Or will it always be 9

a451 = 4 + 9(450)

Through explicitly forumula of an = a1 +d(n-1)

@glass condor this correct?

[uncut matrix]

if I'm struggling with this MIT textbook I'm using to study discrete math, should I just use something else?

just can't figure out how to prove things using the well ordering principle

yes I understand it involves finding a contradiction, either that the set is empty or there exists a number less than the least number

but actually being to apply it to solve a proof is just extremely confusing for me

[faint narwhal]

Not sure if this is really a problem with the textbook you're using. Seems like you just need more practice using it

[uncut matrix]

I've tried reading the explanation again and again

tried doing the questions and I can't solve anything using it

the stuff with applying it to the sum of consecutive numbers to prove 1 + 2 + ... + n = n(n+1)/2 still doesn't make sense to me

[faint narwhal]

Uh, that seems more like an induction question, and not well ordering principle

[uncut matrix]

https://i.imgur.com/aXyunQm.png
https://i.imgur.com/QsWPbn6.png

[faint narwhal]

Okay yeah this isn't super standard

Usually people call this method induction (although it is implied by well ordering)

[uncut matrix]

oh hm

[faint narwhal]

What here aren't you understanding?

[uncut matrix]

Since c is the smallest counterexample, we know (2.1 which refers to 1 + 2 + ... + n = n(n+1)/2) is false for n = c, but true for all nonnegative integers n < c. But the theorem is true for n = 0, so c > 0. This means c - 1 is a nonnegative integer, and since it is less than c, the equation is true for c - 1

for starters, why are they trying to test n = c?

n refers to the # of terms in this equation, yes but

[faint narwhal]

You're trying to prove that it holds true for all natural numbers n. So we take an arbitrary natural number c and show that it holds true for c

[uncut matrix]

why would it be false for n = c but true for n = 0 though?

if n = 0, then there are no terms in the set(?)

0(0+1)/2 is just 0

[faint narwhal]

Sure, I guess this is a bit of a technicality. You're right that we're not summing things on the left hand side, but usually we assign the value 0 to this "empty sum"

and this is a pretty common thing to do

If this bothers you, everything goes through if you just change all the 0's to 1s and like nonnegatives to positives and start your natural numbers at 1

[uncut matrix]

hm ...

so since there exists a 0 in the set regardless it's not empty

and assuming all positive integers, there exists an element (denoted c here) which is a least element

isn't n = c true for n = 1 by the way?

because then the equation would just equal one and there'd exist c = 1 which is the least element in the set

ofc if n = c = 2 then it wouldn't be correct because the set would contain 1 + 2 and 1 is obviously smaller than c, which is then equal to 2

[faint narwhal]

I think you're confused about the set C. The set C is defined as all elements that don't satisfy the inequality

Since we're trying to prove the statement, we're trying to show that the set C is empty

The set isn't the numbers 1 + 2 + 3 + ... + n

The set C contains the values of n such that 1 + 2 + 3 + ... + n is not equal to n(n+1)/2

[uncut matrix]

okay, so just taking base cases then ...

wait no I'm just confused

how would you go about proving this then?

I don't really see how somebody to come up with c-1 to draw a contradiction with

[faint narwhal]

So c is the smallest element in C

that means that c -1 is not in C, because it is smaller than c

[plucky patio]

Hello! Is it okay if I ask a quick question about set notation here?

[haughty garden]

yes

[uncut matrix]

so always try to take a number smaller than the least number?

and try to use to find a contradiction since it belongs in the set?

[plucky patio]

If A is a set, then what does {A_i}_i^k mean?

[faint narwhal]

Well, you always take one less than the smallest number

since that is the only way you can guarantee that its still nonnegative

if you take c - 2 for example, that could end up being negative

[uncut matrix]

ah

[faint narwhal]

yes you use that to try to create a contradiction

Since you know the statement is true for c-1, you try to use that to show that the statement is true for c

[uncut matrix]

hm, so if I try to apply this to a different problem

say

prove: every amount of postage that can be assembled using only 10 cent and
15 cent stamps is divisible by 5.

the set would equal every amount of postage that can be assembled using 10 cents and 15 cent stamps is NOT DIVISIBLE by 5

assume the set is not empty and contains non-negative integers, hence there exists an element c that is the least number

for c - 1, the set is true

[faint narwhal]

Well okay, this ends up being a bit different

because you're not trying to prove something holds true for all integers n

[uncut matrix]

that's true

I just want to know whether it's divisible by 5 or not

[faint narwhal]

you can apply a similar idea though

basically instead of looking at c-1, look at either c - 15 or c - 10

[uncut matrix]

hmmm

[faint narwhal]

since c was assembled using some combination of 10 and 15 cent stamps, you can remove one of these stamps to get a value of c - 10 or c - 15 and then apply similar ideas

[uncut matrix]

so then I have to prove c - 10 or c - 15 is divisible by 5

and that creates a contradiction because c should be the smallest integer that's divisible by 5

[weary tiger]

what does Un mean?

[minor dagger]

In what context?

[weary tiger]

General terms and sequences

[minor dagger]

it's just the nth term

I think usually a subscript like n refers to the nth value of some index

[turbid kestrel]

@weary tiger

[weary tiger]

hiii

[turbid kestrel]

Discrete

[weary tiger]

ik

[turbid kestrel]

Ok

Pov a ninth grader looking at this 😳😳

[weary tiger]

oh lmao

[turbid kestrel]

😂 sheeesh

I got the hw done

[weary tiger]

oh, congo

[shut fjord]

This is a dynamic programming problem, we are tasked with just creating a recurrence relation for now

Here’s my work so far, but I can’t really grasp a pattern:

Thought that something was going on with combinations but I abandoned this idea

Then I thought of how they were smaller problems.. but again I’m stuck

[mystic moss]

@shut fjord it's like the one you did earlier, except with less cases

[shut fjord]

I think there's only one base case

or 3