discrete-math

[spare jolt]

well, maths isn't really directed towards "self-learners" like programming.

[distant bay]

but beyond that I've been reading that calculus and discrete maths doesn't really overlap

[spare jolt]

well it depends on the concept, there are many concepts in discrete mathematics which can be formally proven and defined using concepts in often taught in calculus

[spare jolt]

Anyone know whether or not this is true?

$$\left(1-x\right)^{-n}=\sum _{k=0}^{\infty }x^k\binom{n+k-1}{k}$$

[vital dew]

Soap:

Soap:

[spare jolt]

nvm got it

[weary tiger]

Hey guys

Is it possible if someone can check my work

Just wanna know if it's right

[stray reef]

it's not

just because 4 R 4 does not mean x R x for all x.

and in fact, there is a counterexample to x R x

[weary tiger]

Please explain sorry I'm new to this

What do u mean? For all x?

Would 5 R 5 be a counter example?

And how would I format it properly?

[stray reef]

"5 R 5 is false, because 5 + 5 = 10, and 10 is not divisible by 4.
since 5 R 5 is false, the relation R is not reflexive."

you should know by this point that a relation is called reflexive if and only if it satisfies xRx for all x in its domain.

(∀x ∈ X)(xRx), if X is taken as the domain of R.

[weary tiger]

Ah alright I get it now

For this problem tho

There are multiple cases for transiitive right

Transitive*

[stray reef]

wdym

[weary tiger]

I put it's not transitive for odd numbers or if the x and y are even and not the same number

[stray reef]

you need to establish whether it is true that for all x, y, z in N, if x+y is divisible by 4 and y+z is also divisible by 4, then so is x+z

it's not "not transitive for odd numbers"

"transitive" describes the relation as a whole

your answer to "is this relation transitive?" can only be "yes it is transitive" or "no it is not transitive"

[weary tiger]

Well since it's only transitive when the numbers are even and the same, which would mean x=6 y=6 and z=6 for example lol

[stray reef]

no

[weary tiger]

That means it's not

Transitive

[stray reef]

"it's only transitive when ..."

no

that's bad wording

[weary tiger]

I mean that's not what I would write

Just explaining to u

[stray reef]

my point still stands

[weary tiger]

It's not transitive then

Dang this function is only symmetric

That's a first lol

[stray reef]

this is not a function

it's a relation but it is not a function

[weary tiger]

Ah yeah relation my bad

How would I know if it's an equivalence or partial order?

[stray reef]

there are checklists for both of those things

to be an equivalence relation, you need all of the following properties:

• reflexive
• symmetric
• transitive

to be a partial order relation, you need all of the following properties:

• reflexive
• transitive
• antisymmetric

[weary tiger]

lol my relation is neither, only symmetric

thanks for the help

[urban olive]

I need help guys

I need to see if there is a tautology in this proposition or not using the laws of equivalence

But I dunno where to start

[halcyon ledge]

hmm get rid of the implication

[urban olive]

How?

[halcyon ledge]

$a \rightarrow b$

[vital dew]

deekaan:

[halcyon ledge]

$\neg a \lor \ b$

[vital dew]

deekaan:

[halcyon ledge]

so those two are equivalent

[urban olive]

So I will have ~(p ^ q) v (p v q) ?

[halcyon ledge]

yes

then you translate the first term in its equivalence

and you're pretty much done

[urban olive]

Aight let me see if I can do it by myself

Ty

[halcyon ledge]

no worries

[urban olive]

@halcyon ledge (~p ^ ~q) v (p v q)

Now what? I'm stuck again

[stray reef]

nope

$\neg (p \land q) \neq \neg p \land \neg q$

[vital dew]

Ann:

[urban olive]

Oh so (~p v ~q) v (p v q)

@stray reef

[stray reef]

yeah that's what it'd be

[urban olive]

So how can I demostrate that is a tautology?

That's what I have to do

[stray reef]

well you've got four things or'd together

two of them are ~p and p

[urban olive]

That is a tautology iirc

[halcyon ledge]

ya or is commutative

but you could just stop at this point

[urban olive]

This is what my book says

[halcyon ledge]

yes

[urban olive]

t = tautology

So the other expression (p v q) is a tautology too?

[halcyon ledge]

no

the entire expression is a tautology

https://cdn.discordapp.com/attachments/496785905474994186/711965079586865162/unknown.png

that's the tautology

[urban olive]

Ohh I see, thank u guys

❤️

[weary tiger]

Hey guys does anyone know how to continue this set algebra simplification?

[halcyon ledge]

whats in the intersection of A and of complement A?

[weary tiger]

Where exactly?

[halcyon ledge]

second term bro

[weary tiger]

That's a union I think dude

[halcyon ledge]

the third line

read it slowly

you'll see A intersects complement of A

[weary tiger]

Ah I see it yeah

[halcyon ledge]

that one should be easy

[weary tiger]

Isn't it A

[halcyon ledge]

no

[weary tiger]

Oh hold up is it no set

[halcyon ledge]

yes it's empty

[weary tiger]

Ah aight

[halcyon ledge]

okay that makees things easier

[weary tiger]

Is the work so far correct?

[halcyon ledge]

now substitute A intersects complement of B with X

[weary tiger]

X??

[halcyon ledge]

yes

[weary tiger]

Never heard of that sorry

[halcyon ledge]

you never heard of X

[weary tiger]

Is that like a rule

I mean in set algebra I never used x

[halcyon ledge]

it'll make things easier for your brain

[weary tiger]

Ah ok

[halcyon ledge]

substitution is your friend

[weary tiger]

Lol

[halcyon ledge]

Once thats done you have a term you should know how to deal with X union (A intersect C)

[weary tiger]

alright I'll solve it now

Thanks a lot

[halcyon ledge]

no worries

don't forget to resubstitute

[weary tiger]

Ye

[whole shard]

hello can someone explain how su<tv came up?

[last sigil]

All it is saying is that if a, b, c, d are positive, and a < b and c < d, then ac < bd

This is necessary for the next step, where you apply this to sqrt(n) < a & sqrt(n) < b

[whole shard]

oh so i treat it like regular algebra? but its > or <?

thx

[weary tiger]

@stray reef this is proper wording right?

[stray reef]

hrngh

no, i wouldn't say so

"6R8 and 8R12, but 6 R 12"

"therefore R is not transitive"

also i'd change "for example" to "counterexample"

[weary tiger]

Counter example?

Ah I see

Cuz it's countering the transitive property

Alright

Thank you

[whole shard]

cosmic what topic is that

@weary tiger

[weary tiger]

Properties of relations why

@whole shard

[whole shard]

I'm reviewing Proofs, and the question looked so similar, but your solution is weird.

We havent gotten to that topic thats why

[weary tiger]

Ah ok

Good luck

[whole shard]

Thx

[whole shard]

Can someone translate this for me? 😮

[pale epoch]

into what language?

[whole shard]

p,q,r,s

how is ~p built to be "at most three of the 22 days fall on the same days of the week"

i thought a negation would be.. "Not"

[pale epoch]

negation is more like opposite

[whole shard]

i just dont undestand how "at most three days" is the opposite of "at least for days"

[pale epoch]

well

if you know that at least four days sth is wrong

then you know sth is not happening on 4, 5, 6, ... days

so it must happen at most 3 days

so 0, 1, 2 or 3

this is kinda paraphrased, but ...

maybe it is clearer if you first think of a specific day

the opposite of "at least 4 of the 22 days fall on a monday" is "at most 3 days fall on a monday"

because the first is equivalent to "4 or 5 or 6 or ... or 22 of the days fall on a monday"

and if that is not true, then you know that "0 or 1 or 2 or 3 days fall on a monday" must be true

i.e. "at most 3 days fall on a monday"

[whole shard]

oh okay

i understand now, thank you

[prisma arch]

need some help having a hard time getting how id go about A. Like i know its a combination issue because order doesnt matter but im not sure if its something like C(7,1) + C(9,4) or if theres more to it

[sacred furnace]

Does this show one-to-one correspondence? Meaning one-to-one and onto. I'm not sure if I did it right.

[sleek swallow]

Well, clearly, it's not injective. If n = 3, then 2^3 = 8 but you can have two strings 1011 and 1101 that would be preimages of 8.

[sacred furnace]

ahh ya good point

[sleek swallow]

Indeed, it was a good point.

[sacred furnace]

lol

i guess im unsure of how to start this problem, any suggestions abhijeet?

[sleek swallow]

Well, which one? You've shown that it's not injective. Now, you're trying to prove or disprove the claim that the function is surjective, right?

So, how will you approach it?

[sacred furnace]

could i swap the domain and codomain of the ordered pairs i found, and if f(x)=y then it is onto?

[sleek swallow]

You need to show that $f(S) = \bZ^+$. You already know that $f(S) \subset \bZ^+$. Now, you need to show that $\bZ^+ \subset f(S)$.

Suppose we have an integer that isn't a power of 2. So, something like 3, for example. Then, it's clear that $n$ is not going to be a natural number. We certainly can't find a bit string such that the sum of all the digits in the bit string is $\log_2(3)$. So, this function cannot be surjective.

[vital dew]

Abhijeet Vats:

[sacred furnace]

nice good explanation

im not really sure how i showed that it was not injective? Esecially after you mentioned that there is more than one way to arrange the bitstring to get the sum

[sleek swallow]

Well, a function $f:A \to B$ is injective iff $f(x_1) = f(x_2) \implies x_1 = x_2$. In other words, every image must have a unique pre-image.

[vital dew]

Abhijeet Vats:

[sleek swallow]

In this case, if 8 is what we're concerned with, then n = 3 is the sum of the digits in the bitstring. However, 1011 and 1101 both yield a sum of 3 when we add their digits together. In other words, 8 has two preimages.

So f(1101) = f(1011) = 8 but 1101 =/ 1011

[sacred furnace]

making it not injective

nice

[sleek swallow]

Yeap, that proves that it is neither injective nor surjective.

[sacred furnace]

yeah, nice i think i got the neccessary explaination in order to do it thank you

[sleek swallow]

You're welcome.

[weary tiger]

Hey guys is this circuit correct for the equation

[whole shard]

can i ask what chapter is that

[sacred furnace]

https://cdn.discordapp.com/attachments/442470054978650122/712055933936599110/IMG_20200518_1434502842.jpg

My method of iteration, that I am emulating from my notes is not working
Would it be possible to get help on how to find an explicit formula?

[sleek swallow]

$a_1 = 3a_0 - 5$

$a_2 = 3a_1-5 = 3^2a_0 - 5 \cdot 3 -5$

$a_3 = 3a_2-5 = 3^3a_0 - 5 \cdot 3^2 - 5 \cdot 3 - 5$

So, looking at the pattern that's developing, it stands to reason that:

$a_n = 3^n - 5(3^{n-1}+3^{n-2}+\ldots+1)$

[vital dew]

Abhijeet Vats:

[sleek swallow]

Now, simplify that by recognizing that the there is a geometric series in there

And use that to find a_10

@sacred furnace

Let me know if you have any other difficulties

[sacred furnace]

Thanks again Abhijeet, I am having trouble finding the common ratio. I know to find it you can divide a_2/a_1. But this ratio does not hold for the sequence

[sleek swallow]

No, there isn't a common ratio in the terms of this sequence.

However, there is a geometric series in the general term $a_n$

[vital dew]

Abhijeet Vats:

[sleek swallow]

Can you see it?

[sacred furnace]

$-5(3)^{n}$

[vital dew]

chrondo:

[sleek swallow]

Nope. It's $3^{n-1}+3^{n-2}+\ldots+1$. That's your geometric series in the general term.

[vital dew]

Abhijeet Vats:

[sacred furnace]

Where a_1 =1 and r=3^(n-1) ?

[sleek swallow]

Wut

[sacred furnace]

Well a geometric series is a_1(r)^(n+1) ?

[sleek swallow]

No

[sacred furnace]

Actually I guess r might be 1/3

[sleek swallow]

A geometric sequence has the following form:

$a,ar,ar^2,ar^3,\ldots$

A geometric series is, then, either a finite or infinite sum:

$a+ar+ar^2+ar^3+\ldots$

[vital dew]

Abhijeet Vats:

[sleek swallow]

You don't have to guess

This isn't something that requires a guess

@sacred furnace Do you understand the pattern developing above?

[sacred furnace]

All until a_n

[sleek swallow]

So you're not sure how I got a_n?

[sacred furnace]

Well when I try to plug in a_4 for example.into a_n, I get -59

But a_4 should be -119

So I'm about -60 off

[sleek swallow]

You made a calculation mistake in using the formula above

Try calculating it again when n = 4

[sacred furnace]

oh ya

youre right

[sleek swallow]

Nope

See, the geometric series we want to get a general formula for is this:

$$S_n = \sum_{k=0}^{n-1} 3^k$$

[vital dew]

Abhijeet Vats:

[sleek swallow]

What you've written is just a few terms from that series

[sacred furnace]

$a_n = 3^n - 5$\sum{k=0}^{n-1} 3^k$$

[vital dew]

chrondo:
Compile Error! Click the reaction for details. (You may edit your message)

[sacred furnace]

i have this example

[sleek swallow]

Yeap it's exactly the same idea

Conceptually, the two problems are not difficult

[sleek swallow]

Wow, why does that look like it was written by a 5 year old

But yea, it looks correct 🙂

[sacred furnace]

I kinda scratched it out

But ya, ok, that took awhile, but thanks for your patience

[sleek swallow]

You're welcome.

[weary tiger]

What would be the best algorithm for 'dividing equally a cake' between 3 people? Obviously im assuming the cake is not the same on any one third of it, players having preferences. Let me clear it up on 2 player game, where best algorithm is that one player divides the cake into 2 equal halves from his point of view and the 2nd one picks one of the two he prefers. I found a 3 player one but I think there would be faster one

[last sigil]

||https://en.wikipedia.org/wiki/Fair_cake-cutting#2_people_–_proportional_and_envy-free_division||

[weary tiger]

Oh lol so thats a thing ok

[last sigil]

Yeah spooky

I found a mathexchange post on it as well

https://math.stackexchange.com/questions/637728/splitting-a-sandwich-and-not-feeling-deceived

[weary tiger]

Yeah I found 6 cuts and the best one seems to be 5

[reef thistle]

@neon thorn what you can do is find their gcd and divide that out one of the moduli

If not coprime, existence is not guaranteed, consider 2 mod 4 and 1 mod 2

gcd of 2, 4

the gcd is 2

because they would be independent

anything one modulus claims has no bearing on what it is in the other modulus

it can lead to no solutions, yes

[stray reef]

try x = 1 (mod 2) and x = 0 (mod 4)

yeah well there you have it

[faint narwhal]

Yes

But when your moduli aren't coprime and you do have a solution, you again have a unique solution

Since for example, the system

x = 0 (mod 2) and x = 0 (mod 4)

Has the exact same solutions as x = 0 (mod 4)

yes

[spare jolt]

oh, right, how would have solved it?

4 couples (8 people), and making sure each couple is together, I want to place them in a line.

Yep

Well, 4

So I assumed (4)!

Right, but if you did that

The other couples wouldnt be able to

Be next to each other.

Yeah, tho the one that was confusing me was figuring out all the situations where "no couple" is sitting next to each other.

Yeah I guess.

I'll give it a go

[spare jolt]

Hmm still not sure how to do it so none of the 4 couples are sitting next to each other.
So here's my thinking:
I have 8 people/4 couples: A,a,B,b,C,c,D,d
At first I have 8 choices
A _ _ _ _ _ _ _
But now, I only have 6 choices since a cannot be next to A
So I guess I can put it here:
A _ a _ _ _ _ _
But now if I put B, in between A, I have 5 choices
A B a _ _ _ _ _
But if I put B outside of A, I have 4 choices:
A _ a B _ _ _ _
And I'm not sure how I can account for this.

[runic cedar]

anyone know a good way of finding the values of 3 unknowns that's constrained between Natural 0-40 ? I've got a formula that combines them into a single value and a set of values I need to decode that generates those values but I'm not sure how it would be done.

So as an example. I want to encode ABC, where A = 1, B = 2, C = 3
I can encode it as:
A + 41 * B + 41^2 * C
= 1 + 41 * 2 + 41^2 * 3
= 5126

but idk how you'd do it in reverse

[weary tiger]

May someone pls explain this table of predecessors

I usually write it in a different way

so im not sure what this one is trying to say

[runic cedar]

eh who cares about proper decoding techniques. I'll just brute force it 😄

[faint narwhal]

look at the number mod 41

and that will give you A

mod 41 is looking at the remainder when you divide by 41, or the operator % in C

@runic cedar

[runic cedar]

@faint narwhal oh that's pretty neat. Thanks

[faint narwhal]

you can do similar things to find B and C

I'll let you think about it

[runic cedar]

fair. Thanks

[weary tiger]

does anyone here know table of predecessors and hasse diagrams

i need someone to check my work if its possible

[bitter moss]

Fuck discreme maths

All my homies hate discrete maths

[spare jolt]

we're all your homies then

[whole shard]

can someone tell me how the highlighted part came up

i understand under it is factored but I'm not sure why it's necessary to do this when there already an answer above it

[coral totem]

The assumption about P(k) at the top

[whole shard]

Why do we have to add (k+1)? is that the step after P(k+1)

this is not clear to me?

This is the original question

[coral totem]

This is a proof by induction

You show it works for a base case, assume it works for k, then show it works for k+1.

So just above hype first pic you submitted, it should say something like “note: if n=1, we have 1=(1(1+1))/2”

To establish the base case

[whole shard]

Oh yes

I cropped the basic step

[coral totem]

Which is fine

Do you understand why you have to prove the case P(k+1) now?

[whole shard]

the first one was p(k)

the second one is p(k+1)

[coral totem]

Huh?

[whole shard]

???

[coral totem]

The first one was p(1)

For p(k) all you did was assume your formula worked

[whole shard]

okay but come it added another (k+1)?

[coral totem]

Because you aren’t just adding up the first k integers anymore, you’re adding up the first (k+1) integers now

If you look at my blue highlighted pic, you notice I didn’t highlight the (k+1) on either side

[whole shard]

yes

[coral totem]

For the proof itself we have to do this in general, meaning with variables, but let’s just see what happens if we pick something like k=5

[whole shard]

so like p(k) + (k+1)?

[coral totem]

That’s exactly it

[whole shard]

but do they need to have the exact answer?

p(k) = p(k) + (k+1)

[coral totem]

It should be p(k+1) = p(k) + k+ 1

[whole shard]

AH

now this one is a problem

Where did (2k-1) come from? shouldn't it be k?

And I know that odd numbers are (2k+1)

[sleek swallow]

?

2k-1 works perfectly well as a representation of an odd number

[whole shard]

is there a reason why it chooses that vs the regular one

[sleek swallow]

Look at the original statement of the problem. Like, look at the result that's being proved

[brittle marsh]

hey how can i prove that this function is Surjective?
h: N -> 2N
2N represents even natural numbers.

h(n)=2n

[pale epoch]

by giving a pre-image for every element of $2\mathbb{N}$

[brittle marsh]

like 2?

and 2n=2

n=1

[vital dew]

Lochverstärker:

[pale epoch]

what

is 2 every element of 2N?

[brittle marsh]

no

[pale epoch]

then that won't do

@neon thorn do you not have precise definition of big o and little o

your understanding of big-oh is wrong

[brittle marsh]

what is a pre-image for even numbers?

[pale epoch]

do you know what a pre-image is?

[brittle marsh]

i know what a "image" is but im not sure about pre-image

[pale epoch]

ok, take your function h(n) = 2n

if you plug in 1, you get h(1) = 2

so 1 is the preimage of 2

and 2 is the image of 1

both under the function h

that is the terminology

and what you have to do is take an arbitrary even number

and show that there is a preimage under h

[brittle marsh]

i see.

[pale epoch]

i.e. that there is a natural number n, such that h(n) = your arbitrary even number

[brittle marsh]

can it be h(2n)?

h(2n)=2(2n) =4n?

and 4n will always be a even number

can i conclude thaT?

[pale epoch]

no

you have to show that every even number has a preimage

like, 6 is even, but you can't write 6 in the form 4n

so this argument doesnt work for 6

[brittle marsh]

hum, okay

but if n is a natural number all even numbers have an n

[pale epoch]

what

[brittle marsh]

h(n)=2n if n is natural number 1,2,3...

h(1)=2, even
h(2)=4, even
h(3)=6, even

etc...

[pale epoch]

yes, but that is not what you have to show

[brittle marsh]

uhm

[pale epoch]

ok, so

[brittle marsh]

i have to show that for all image have one pre-image right?

[pale epoch]

at least one preimage

but yeah, in this case it will even be unique

take your function h

what's the preimage of 128?

[brittle marsh]

128/2?

[pale epoch]

yes

what's the preimage of 60004562

[brittle marsh]

/2

[pale epoch]

yes

how do you represent an arbitrary even number?

[brittle marsh]

n/2

[pale epoch]

no, you don't

[brittle marsh]

2n/2

[pale epoch]

that's just n

what is n?

[brittle marsh]

a natural number

[pale epoch]

(2*1)/2 = 1

that's not an even number

(i plugged in n=1)

[brittle marsh]

i see

but 1 is a natural number right?

[pale epoch]

yes

@neon thorn ye, that's somewhat better. ofc you can think more methodically about this, by writing down exact definition of big/little-oh, but i would say that you will find examples pretty fast by just trying

try more "traditional" functions that appear in big oh notation

also, your functions are weird anyway

they are defined in terms of n, which makes no sense

and x! isnt even defined if x is not a natural number

(at least not without some more thought)

[brittle marsh]

hey loch thank you

[urban olive]

Hello again

So I have this preposition: (~p ^ (p -> q)) -> ~q

Need to check if there's a tautology or not

But I'm stuck and dunno where to start

[sleek swallow]

Try to find a falsifying assignment of truth values

[urban olive]

How do I find that?

[sleek swallow]

Assume that the entire statement is false.

[urban olive]

Also I forgot to mention

I need to use the equivalency laws

To demonstrate that

[sleek swallow]

Then, the antecedent is true and not(q) is false. Hence, q is true.

Now, if the antecedent is true, that means that not(p) is true. So, p is false. Now, p is false and q is true. Clearly false implies true is true. You've successfully found an assignment of truth values that cause the statement to be false. It's not a tautology

-.- Make sure you mention such things beforehand

[urban olive]

Yeah sorry

[sleek swallow]

Have you attempted to reduce it into a series of equivalences?

[brittle marsh]

hey @pale epoch u know what equipotent is?

[urban olive]

@sleek swallow yeah I got it, thx anyway

[sleek swallow]

Aight

[toxic raven]

Hey guys, sorry if this is a silly question, but can this be classed as Symmetric or not because it has -1 and 1, so I wasn't sure if a negative/positive of the same number counted as a factor. Thanks!

[halcyon ledge]

well symmetric means if (a,b) exists so (b,a) as well

-1 and 1 are obviously different elements

[toxic raven]

I got (1, -1) => (-1, -1)

but it would need to be (1, -1) => (-1, 1) to be symmetric right?

[halcyon ledge]

yes

what youre saying is -1 <= 1 therefore -1 <= -1

because the relation is symmetric

it makes no sense

[toxic raven]

got ya. thank you for your help!

[whole shard]

is that topic about relation?

[clever patrol]

ye

[prisma arch]

need some help getting around this

I have the following work but Im stuck

This is involving combinations and permutations

[whole shard]

can someone explain to me how he got to the last one

its not making sense

[halcyon ledge]

by putting the 2 into the exponent

$2 * 2^2 = 2^3$

[vital dew]

deekaan:

[halcyon ledge]

now in sexy latex

[whole shard]

but look it says $2^k+1 + 2^k+1 $

[vital dew]

Yo Mama:

[whole shard]

did that work

$2^(k+1) + 2^(k+1) $

[vital dew]

Yo Mama:

[halcyon ledge]

put curly braces around the k + 1

${$

[vital dew]

deekaan:

[whole shard]

$2^{k+1} + 2^{k+1} $

[vital dew]

Yo Mama:

[whole shard]

oh yes

[halcyon ledge]

$2^{k+1} + 2^{k+1} = 2(2^{k +1})$

[vital dew]

deekaan:

[halcyon ledge]

its like $a + a = 2a$

[vital dew]

deekaan:

[whole shard]

oh like it became a variable lol

that was a hard one to see

[halcyon ledge]

something like that sure

but now you know the trick and recognize is when it pops up again

[whole shard]

yes im reading examples sometimes it does that

but how come it became k+2

😩

[halcyon ledge]

uhh let k = 3

$2^{k+1} = 2^4 = 2 * 2 * 2 * 2$

[vital dew]

deekaan:

[halcyon ledge]

and $2* 2^{k} = 2^{k+1} = 2^{4}$

[vital dew]

deekaan:

[halcyon ledge]

and $2 * 2 * 2^k = 2^{k+2} = 2^5$

[vital dew]

deekaan:

[whole shard]

ah exponent rule?

like $x*x=x^{2}$

[vital dew]

Yo Mama:

[whole shard]

or something about power

@halcyon ledge

what even happened here

[sleek swallow]

It's just algebra

See that second term?

That was just put over the same denominator as that of the first term

[whole shard]

i just couldnt figure out how the addition in the numerator happened

[sleek swallow]

Have you understood it now?

[whole shard]

OPS

hyes

yes

[sleek swallow]

Alright good.

[whole shard]

it cancelled thank you

[sleek swallow]

Yeap

[whole shard]

can u provide feedback

maybe i shouldve solved for the $(k+2)^{2}

$(k+2)^{2}$

[vital dew]

Yo Mama:

[pale epoch]

what are you even doing

[sleek swallow]

HAHA lmao

[pale epoch]

you should spend less time on boxing random fractions and more time on writing actual words

[whole shard]

i think im solving the problem using math induction

[sleek swallow]

Yo mama, p(k) is not a polynomial. It's a proposition. More specifically, it's the statement that:

$\sum_{k=1}^{n}k^3 = \frac{n^2(n+1)^2}{4}$

[pale epoch]

ok, i dont see that

[vital dew]

Abhijeet Vats:

[halcyon ledge]

not bad wouldn't have been able to tell from just looking at it

[sleek swallow]

Also, you think that you're solving it using induction?

[pale epoch]

at one point you start an equation with =

and at one point you end one with a random =

[whole shard]

no no im on mathematical induction

[halcyon ledge]

$\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + (n + 1)$

[vital dew]

deekaan:

[pale epoch]

you should explain with words what you are doing

maybe then you would notice that you are doing nonsense

[whole shard]

is this problem solved by something else?

[pale epoch]

no

you are supposed to do induction

[whole shard]

yes i did the induction, but the bottom is not matching

[sleek swallow]

You're not using induction

[whole shard]

i thought i did right

HUH

[sleek swallow]

You've written some random gibberish that doesn't make sense

[pale epoch]

try explaining it in words

[whole shard]

Oh i have to write the words as well?

[pale epoch]

math is not a magic spell, where you write down random symbols that make a proof

[sleek swallow]

You've tried to use induction in skeleton of the argument. But write words and explain what you're doing

[pale epoch]

generally you should explain what you are doing, if you want people to understand you

[whole shard]

OH okay okay

[pale epoch]

a proof is not a string of mathematical symbols

its an argument

it should at least involve a few sentences

[whole shard]

let me try again

[halcyon ledge]

use my hint!

[whole shard]

i def thought that the senteces in my book was just explaining me how the steps are done

[prisma arch]

Can I also get some help with the problem I posted earlier?

[halcyon ledge]

well and now you're trying convince us that the thing youre trying to proof is true

what problem?

[prisma arch]

lol posted it earlier but i can do it again

One sec while I show what I have so far

[halcyon ledge]

from induction to this oof

[prisma arch]

I know this is more low level but I do need help with it

[halcyon ledge]

well lets start with one restriction

all positive integers less than 1000000 with exactly one 9

how many?

[prisma arch]

right so then it would be 999,999 and lesser except 0

no negatives as well

[halcyon ledge]

yes

0 - 999999 with exactly one 9

[prisma arch]

right and so because i need the 9 I can subtract that from the sum i need from the numbers which is 13 -9 = 4

so the remaining ints would have to add up to 4

that would be 2+2, 3+1, and 4+0

so i know i have to do the possible combinations for (9,2,2) (9,4) (9,3,1) with the rest of the integers being 0 but I just dont know how to setup the combinations or permutation equations to it

[sleek swallow]

You're forgetting that you could also have 1+1+1+1 or 2+1+1 or 3+1 or 2+2 or 4+0

Do it case by case

Not quite sure if there's an elegant way to do this right off the top of my head

[prisma arch]

oh man you are right with the 1's

Im sure there is an elegant way to do it because for example the 9 with 4 there would be a ton of combinations if you have to fit it within a 6 digit number

[sleek swallow]

You can build up restrictions on the number of digits. For example, if it was the case that this number had a single 9 in it and had 4 1's, then it has to be at least a 5 digit number. So, you can handle two cases over there

If it had a single 9 and a single 2 and two 1's, then it has to be at least a 4 digit number. So, you can do the calculation like that

[pale epoch]

cant you just think of 6 slots, fill any one with 9

and fill the others such that the sum is wtv u want

there are x ways to choose digits, position anywhere

[whole shard]

Is this better

[pale epoch]

fill anything else with 0

[whole shard]

but the bottom is hard to fix

[pale epoch]

yes, this is better

now i can see where you are going wrong

why do you assume p(k) \implies p(k+1), isn't that what you want to prove?

[sleek swallow]

Loch, there aren't just 6 slots. You have to consider 5 digit, 4 digit numbers and so on

[pale epoch]

what is p(k) = something supposed to mean

you stated that p(k) is a proposition, so how am i supposed to understand this?

[prisma arch]

Hmmm

[whole shard]

oh so we want to prove p(k+1) is true

okay okay

[pale epoch]

the sum below that does not make sense

you are adding popositions to a sum of numbers

[prisma arch]

I think I will probably schedule and appointment with my prof

[pale epoch]

yes, but just fill the empty slots with 0s

[sleek swallow]

But loch's point can basically be extended, Red. You can consider the amount for 6 digit numbers, then for 5 digit numbers etc

[pale epoch]

and you will produce 4 digits numbers

and anything possible

[weary tiger]

yo abhijeet

[sleek swallow]

Hallo friend

[whole shard]

sorry i figured out the problem thank uu again

[pale epoch]

ok, my idea is pretty much the same you did

[whole shard]

so my wording was wrong

[sleek swallow]

The same who did? Me?

[pale epoch]

ye

[sleek swallow]

No u

[pale epoch]

thanks

@whole shard not just your wording is wrong

you also seem to be doing something wrong in the inductive step

[whole shard]

huh

[pale epoch]

but it's hard to tell exactly what and why, if you don't explain your reasoning

[whole shard]

oh so including in the inductive steps i need my wording?

[pale epoch]

you should explain what you do any why

like the equals sign where you wrote IH above, that is good

but you formulated your hypothesis wrong, so im not sure what to make of it

and you used it wrong

you used a lot more than what your hypothesis should be

and like

what is your end result supposed to signify

[whole shard]

i want to prove p(k+1) true

[pale epoch]

you have to prove p(k+1) assuming p(k)

yes, but you didnt

you defined p(n) correctly in your latest pic

so what is p(k+1)?

its not whatever you boxed

[whole shard]

yes the box part is hard, im working on it

i need to make it $(k+2)^{2}$

[vital dew]

Yo Mama:

[pale epoch]

you can't

what you are starting with is already wrong

[whole shard]

my equation is wrong?

[pale epoch]

what equation?

[whole shard]

its p(k)+p(k+1)

[pale epoch]

i cant tell what you are actually working with, because you add 2 propositions to a sum

and the sum has an n in it, that you promptly ignore

[halcyon ledge]

😦

[whole shard]

oh okay let me rewwrite everything

[pale epoch]

and you dont use your induction hypothesis

at least not correctly

[halcyon ledge]

$\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + (n + 1)$

[vital dew]

deekaan:

[halcyon ledge]

@whole shard look at this

its a hint

[pale epoch]

tbh i dont even think he needs the hint, he has more of a problem with the general structure of how induction works

[whole shard]

AHAH

[pale epoch]

or wtf he is doing overall

his algebra seems ok

[whole shard]

I see it

idk whyi put p(k+1)

it should be p(k)+1?

[pale epoch]

what

[whole shard]

ok

wait let me write

[pale epoch]

do you know what a proposition is?

or did you just use the term because it sounds cool?

[whole shard]

yes statements that are true or false

[pale epoch]

yes

can you add statements to numbers?

[sleek swallow]

[whole shard]

huh

[pale epoch]

let p be the proposition "2 is odd"

whats 3+7+p

[whole shard]

thats 12

[pale epoch]

are you fucking with me

[whole shard]

wait

3+7+2 is odd?

i dont undestand what ur asking me

[pale epoch]

yes

why did you write it down

it makes no sense

yet you wrote down $\sum_{j=0}^nj^3 + p(n) + p(n+1)$

[vital dew]

Lochverstärker:

[pale epoch]

but i don't understand what it is supposed to mean

because p is a true/false statement

and the thing before that is a sum

[whole shard]

i think im starting to undestand

its a proposition

$(n^2(n+1)^2)/4$

[vital dew]

Yo Mama:

[pale epoch]

?

[whole shard]

@pale epoch am i getting closer

[sleek swallow]

Why do you have a random sine curve in the middle of your working

[whole shard]

i was having a hard time building my words

[sleek swallow]

Also, no. That last statement you wrote to the left of the vertical lines doesn't look like anything that makes sense.

[pale epoch]

you are getting closer though

the complete left side is correct

and i can also understand it

wait no

[sleek swallow]

What you want to write is

$\sum_{j=1}^{k+1}j^3 = \sum_{j=1}^{k}j^3 + (k+1)^3$

[vital dew]

Abhijeet Vats:

[sleek swallow]

It's not correct, loch

[pale epoch]

yes, i didnt notice

maybe im too tired

[whole shard]

sorry

ill have to reread the book instead

[pale epoch]

the words are correct

but the sums you set up are weird

like, you dont seem to understand sigma notation

[sleek swallow]

Go to sleeeeeepp

[pale epoch]

and the right side shouldnt really start with a random =

[sleek swallow]

But yea yo mama's gotta understand sigma notation

[pale epoch]

like if your sums were set up correctly

then you would have to prove p(k+1)

which you wrote down almost correctly

i just noticed what this question is actually asking

[whole shard]

i was followig the example form the book

[sleek swallow]

The sums weren't set up correctly. What they wrote was:

$\sum_{j=1}^{n}j^3 \ldots +k = \frac{k^2(k+1)^2}{4}$

[whole shard]

just the layout

[vital dew]

Abhijeet Vats:

[sleek swallow]

It's pretty meaningless

[pale epoch]

ye, thats what i mean

he doesnt understand sigma notation

so my next question would be you to write down $\sum_{j=0}^{10}j^3$ explicitly

[vital dew]

Lochverstärker:

[pale epoch]

so anyways

i had my students derive and prove and explicit formula for $\sum_{j=0}^nj^k$ this week

[vital dew]

Lochverstärker:

[pale epoch]

with k arbitrary

a formula in terms of n

it's an interesting problem

[whole shard]

I should go back and review that chapter then

summation

thank u

[pale epoch]

i mean if you cant tell what $\sum_{j=0}^{10}j^3$ is, then yeah

[vital dew]

Lochverstärker:

[whole shard]

i know

it goes like

$0^3+1^3+. . . .+10^3$

[vital dew]

Yo Mama:

[pale epoch]

yeah

[sleek swallow]

Is there a general formula for that, though? I know there are inequalities you can construct from that but not an explicit formula, surely?

[pale epoch]

then i would ask you to write it down with n instead of 10

and then with n+1 instead of 10

and then take a closer look at your proposition

[whole shard]

ok wait

[pale epoch]

and what it really says

yeah, there is a general formula

but it's like, not pretty

the interesting thing is, that it is always a polynomial in n

computing the actual coefficients is impossible for large enough k and n i think

[sleek swallow]

Yea it's a polynomial in degree n+1, yea?

[pale epoch]

n is a variable

the degree will be k+1 or something

yeah, should be

like gauss formula is a polynomial of degree 2 in n

and this exercise of degree 4

checks out

[sleek swallow]

n is the exponent in what ya wrote beforehand

But yea it'll be one higher than the highest degree in the sum

[pale epoch]

🤔

[whole shard]

Im going to rewrite it, with a better summation

[pale epoch]

i had my students derive and prove and explicit formula for $\sum_{j=0}^nj^k$ this week
@pale epoch this is correct

[vital dew]

Lochverstärker:

[pale epoch]

and the result will be a polynomial in n of degree k+1 for fixed k

[sleek swallow]

OHHH sorry sorry, i misread

My bad

[pale epoch]

you can actually express the coefficients with binomial coefficients and stirling numbers

and factorial

but i dont think you can easily compute stirling numbers

[sleek swallow]

That sounds interesting. I might try that if I have time this week.

[pale epoch]

its called faulhabers formula

[sleek swallow]

I have lots of shit to do before going to uni

[pale epoch]

yes, if you dont finish your degree in 1 semester you are a literal failure

[sleek swallow]

Exactly

Gotta make sure I finish it in 1/2 a semester if i want to do a masters

1/3 if i wanna be in the top 10%

[whole shard]

OH wait

[sacred furnace]

https://cdn.discordapp.com/attachments/688912738293907478/712424017574887475/IMG_20200519_1457021262.jpg

So this is what I have so far for contrapositive, but I'm not sure where to go from here. Any help would be appreciated.

[sleek swallow]

Right, that looks like a decently good start

So $32k^5+7 = 32k^5+6+1 = 2(16k^5+3)+1$

[vital dew]

Abhijeet Vats:

[sleek swallow]

And since $16k^5+3$ is an integer, the number above must be odd.

[sacred furnace]

Should I let k=1? Is that viable? If so I Could show that n^5+7=39 which is odd

[vital dew]

Abhijeet Vats:

[pale epoch]

you have no control over k

[sleek swallow]

If $n$ is even, that just means that there exists an integer $k$ such that $n = 2k$. Since you don't know what $n$ is, you can't say anything specific about k

[vital dew]

Abhijeet Vats:

[near prawn]

k is a strong independent variable

[pale epoch]

tbh just notice that 32*something is even

and that even + odd = odd

[sleek swallow]

Yea that works too. Being very explicit is probably necessary at this stage

[sacred furnace]

k dont need no man

[whole shard]

is this a betterr summation?

[pale epoch]

not really

[sleek swallow]

NO

[whole shard]

😫

oh

[sleek swallow]

$\sum_{j=1}^{k}j^3 + \ldots +k$ does not make sense at all in the context of the problem you're doing

[vital dew]

Abhijeet Vats:

[pale epoch]

it's quite obvious that you are trying to copy the proof of the gauss formula

without trying to understand what the symbols mean

[whole shard]

no i dont know what gauss formula is

wait i think i know the real one

[pale epoch]

$\sum_{j=0}^nj = \frac{n(n+1)}{2}$

[vital dew]

Lochverstärker:

[pale epoch]

i assume this is the textbook proof you are basing your stuff on

🔮

[sleek swallow]

You don't have a good working knowledge of the summation. So, either stop using it or get a good working knowledge of it first.

[whole shard]

i really want to understand this

give me a moment

[sleek swallow]

I know you do. So either stop using summations or understand how to use them first.

Like, there really is nothing wrong with just writing:

$1^3+2^3+3^3+\ldots+k^3$

[vital dew]

Abhijeet Vats:

[whole shard]

I THNK HTIS IS IT

[sleek swallow]

No

$\sum_{j=1}^{k+1}j^3 = \sum_{j=1}^{k}j^3+(k+1)^3$

[vital dew]

Abhijeet Vats:

[whole shard]

OH I see

[sleek swallow]

What you wrote above doesn't make sense at all. You want to PROVE that:

$\sum_{j=1}^{k+1}j^3 = \frac{(k+1)^2((k+1)+1)^2}{4}$

[vital dew]

Abhijeet Vats:

[whole shard]

yes

thats actually what I want to prove

[sleek swallow]

So you have to show that:

$\sum_{j=1}^{k}j^3+(k+1)^3 = \frac{(k+1)^2((k+1)+1)^2}{4}$

[vital dew]

Abhijeet Vats:

[whole shard]

by proving, you mean using this? $\sum{j=1}^{k+1}j^3 = \sum{j=1}^{k}j^3+(k+1)^3$

[sleek swallow]

[whole shard]

it didnt copy

$\sum{j=1}^{k+1}j^3 = \sum{j=1}^{k}j^3+(k+1)^3$

Is this it

[sleek swallow]

That is just exactly what I wrote above

It doesn't constitute a proof of anything

But you're on the right track

[whole shard]

one small step for a man

let me write the whole thing again

I think i get what everyone is saying now!!!

[pale epoch]

you labeled the wrong equals sign with IH

you used the IH in the next step

[sleek swallow]

? What's IH?

[pale epoch]

induction hypothesis

[sleek swallow]

Oh

Lul wut's that

[whole shard]

OMG TANK U

[sleek swallow]

You got it?

[whole shard]

oh sht I didnt fix the p(k+1)

[sleek swallow]

For the last time

$\sum_{j=1}^{k+1}j^3+\ldots+k+(k+1)$ MEANS ABSOLUTELY NOTHING IN THE CONTEXT OF YOUR PROBLEM

[vital dew]

Abhijeet Vats:

[sleek swallow]

But yes, otherwise those last few lines are fine

[whole shard]

Huh, should it have said solve it by math induction?

becos the topic was math induction

[obtuse lance]

you're like combining two things that mean the same thing while also messing up I think

$\sum_{j=1}^{k+1}j^3$ and $1^3+\cdots+k^3+(k+1)^3$ are the same thing

[vital dew]

Merosity:

[obtuse lance]

but you're like mashing them together like a madman

makes no sense

[sleek swallow]

I've said this many times by this point

[obtuse lance]

I know I saw lol

just thought I'd say it too for fun

[sleek swallow]

Why are you repeatedly doing these things even when I'm telling you not to?

Nah i wasn't directing that at you mero

[whole shard]

Oh its a review for my exam next week

[sleek swallow]

NO

[obtuse lance]

yikes

[sleek swallow]

WHY ARE YOU REPEATEDLY WRITING:

$\sum_{j=1}^{k+1}j^3+\ldots+k+(k+1)$

WHEN I HAVE TOLD YOU THAT IT IS MEANINGLESS IN THE CONTEXT OF YOUR PROBLEM

[vital dew]

Abhijeet Vats:

[whole shard]

i just folowed the book i was reading

[sleek swallow]

Show me where your book has written that

And if it really has written that specific thing, the author deserves a kick in the nuts

[whole shard]

u mean this?

[sleek swallow]

No look

Either use a summation

Or use the notation in the image you just sent

Don't use both at the same time

Especially when what you're writing really doesn't make sense

[obtuse lance]

I'd argue that what he's writing doesn't make sense in any context

it's not clear what writing j^3 + ...+k+(k+1) could even mean

[sleek swallow]

I cound understand if it was something like j^3 + (1+2+3.....+k+(k+1))

Something like that

[whole shard]

AH

[sleek swallow]

But this is not meaningful at all

[whole shard]

just j^3.......+(k+1)

[obtuse lance]

if there was a +1 after the j^3 maybe

"just j^3.......+(k+1)" ?

[whole shard]

oh yes 1 ... +(k+1)

[obtuse lance]

what does that mean

[sleek swallow]

Yo mama, writing j^3 + (1+2+3+.....+k+(k+1)) is not helpful for the problem at all

It doesn't do anything

Either use $\sum_{j=1}^{n}j^3$ or $1^3+2^3+3^3+\ldots+n^3$

[vital dew]

Abhijeet Vats:

[whole shard]

OH

I GET IT

[sleek swallow]

I've told you this a million times at this point

[whole shard]

Now i get it

Thank you

[sleek swallow]

You're welcome.

[whole shard]

summation, looks like im summing everything

adding*

[keen yew]

Anyone know how to solve this?

let P(n) denote the number of alternative parenthesizations of a sequence of n matrices. What is the value of P(6)?

[coral totem]

how many different ways can you set up grouping parenthesis around 6 matrices

I'd start with some smaller numbers of matrices and see if maybe there's a pattern...

like for 2 matrices, AB there's only 1 way

But for 3 matrices, I could do A(BC) or I could do (AB)C, so that's 2

and for 4 matrices, I could do (AB)(CD) or ((AB)C)D or (A(BC))D or A(B(CD)) or...

and I now notice the time stamp and you probably aren't here anymore, but that would be how I started @keen yew

[marsh geode]

how many possible words can i make from the letters 'abcdef' (they don't have to be real words and i cant use each letter more than once)

no, i haven't yet

ok i think i remember it a little now

it would be 6!

im guessing for my question then, the answer would be 6! + 5!+4! +3!+2!+1 if i were to include words with less than 6 letters

for example, what if i wanted to include "a" as a word

[lyric pumice]

6+6*5+6*5*4+6*5*4*3+6*5*4*3*2+6*5*4*3*2*1

[marsh geode]

ok i see what you mean

It’s all good, I understand it more now

Thanks guys

[spare jolt]

So apparently there is some function which tells you the number of ways n cents can be made from 2 and 5 cents.
A better way of saying this would be:

f(n) = Number of solutions for 2x + 5y = n, n is some integer.

How would I figure this out, apparently the recurrence relation:

f(n) = f(n-2) + f(n-5) - f(n-7), n >= 7
f(0) = f(1) = f(3) = 0
f(2) = f(4) = f(5) = f(6) = f(7) = 1

Can do this? Why is this?

Any ideas?

[last sigil]

@spare jolt

I can help with this

[spare jolt]

That would be great

[last sigil]

So let's create a magical function

You wanna climb a staircase

With n steps

You take 1 or 2 steps at a time

Tell me if I go too fast aka interrupt me

[spare jolt]

Yep, so far so good, sounds like induction

[last sigil]

f(n) computed the number of ways to get to step n with 1 or 2 steps

How can we find a way to compute this?

Well the trick is to work backwards

Let's imagine we are at the end

Our location is step n

Are you with me

[spare jolt]

Yes, I am imagining I am at step 12

f(12) = 2

But I am going to work backwards.

[last sigil]

?

F(12) = 2 isn't true

[spare jolt]

No?

[last sigil]

Don't assign a value to f(12)

Ignore that for now

[spare jolt]

Okey dokey

f(12) = ?

And I'm on the 12th step of the staircase

[last sigil]

Where must you have been before step 12? Remember you only go up 1 or 2 steps at a time

Keyword before

[spare jolt]

Well I guess either 10 or 11

[last sigil]

Cool

So do you see why f(12) = f(10) + f(11)?

In order to get to step 12, you either went to step 10 first or step 11 first

[spare jolt]

Sure, right now interpreting + as an 'or' I guess.

[last sigil]

No

The plus is a plus

f(12) = number of ways to get to step 12

[spare jolt]

Ohh yeah, so f(10) + f(11), is because rule of sum, you can't have gone both at the same time.

[last sigil]

Yep

[spare jolt]

f(10), the case where you went up from 10
f(11), the case where you went up from 11

[last sigil]

Exactly

Now how can we evaluate f(10)?

[spare jolt]

Same thing

f(8) + f(9), etc

Deep into recursion we go

[last sigil]

Can you generalize for f(n)?

[spare jolt]

f(n) = f(n-1) + f(n-2)?

[last sigil]

Yep (happens to be Fibonacci here)

But now let's go back to your problem

[spare jolt]

Ah yep so: f(n) = f(n-2) + f(n-5) - f(n-7)

Would imply

[last sigil]

Very important note

[spare jolt]

f(n) came from either:
Took steps from f(n-2) or f(n-5) or f(n-7)

Yea?

Oh wait the minus

[last sigil]

Look carefully at the sign of f(n-7)

[spare jolt]

yea

[last sigil]

Why would we subtract that?

[spare jolt]

Hmm..., probably a duplicate case

[last sigil]

Be more specific

[spare jolt]

Looks a bit like inclusion/exclusion. My guess is that it accounts for the case where both f(n-2) and f(n-5)

Or something like that.

[last sigil]

yeah

[spare jolt]

Apparently there is a double up between coming from step -2 and step -5

[last sigil]

If you look at the previous steps of n -5 and n-2, there is overlap

Reason we care is cause we deal with coins not steps this time

Cause the order of coins doesn't matter here

[spare jolt]

Ah right

[last sigil]

(I encourage you to think this through very deeply)

Quite important distinction

Anyways, you now see the recusion?

[spare jolt]

Yeah, right now I'm seeing it as:
f(n-5), the case where 'n' coins are made out of 5's
f(n-2), the case where 'n' coins are made out of 2's
f(n-7), the case where 'n' coins are made out of both 5's and 2's

I think it looks much like the inclusion/exclusion principle:
|A u B| = |A| + |B| - |A n B|

but in this case I think f(n) = |A n B|?

So |A n B| = |A| + |B| - |A u B|?

Or maybe I did the opposite..

[last sigil]

More rigor
f(n-5), number of ways to get to n-5
f(n-2), number of ways to get to n-2

Now

From f(n-2) we consider from f(n-7) + f(n-4)

Similar with f(n-5)