discrete-math

[errant bear]

what no

its evaluating f(x) @ x=2 and x=3...

ignore r, think of the problem like this "f(x) = x3 − 3x2 + 2x − 4. Prove that there exists a real number x such that 2 <x< 3 and f(x) = 0"

[soft pike]

hello gyus! I love you so much!
okay, now help me please solve this one:

check whether the following relations are true

Thank you all! Love you! \m/.

[robust mango]

you can do it with truth table

[spare jolt]

truth tables suck

[sleek swallow]

@soft pike Use the definition of each logical connective and truth tables to determine if the given expressions are equivalent or not.

[soft pike]

i try do it like this one

its what i've get after true table fill

[spare jolt]

x & (y -> z) = (x & y) -> (x & z)
x & (!y | z) = (x & y) -> (x & z)
(x & !y) | (x & z) = (x & y) -> (x & z)

maybe i messed it up, but i dont think 1) are equal.

[soft pike]

but they doesn't equals ;D

[spare jolt]

oh okay, so i got it right

[soft pike]

with my two tables

[sleek swallow]

Their truth tables, if you've done them correctly, are not the same. So, they're not equivalent

[spare jolt]

You can also see cuz (x & !y) | is not (x & y) ->

[soft pike]

@sleek swallow two tables must equals to each other for '=' answer?

[sleek swallow]

Yeap. Two logical expressions are equivalent if their truth tables are the same.

[spare jolt]

If two tables are equal, the two statements are equal

I find truth tables a bit exhaustive though. I find it easier to use algebra.

[soft pike]

@spare jolt @sleek swallow tank you gyus for your time!

[sleek swallow]

You're welcome.

[spare jolt]

I just noticed they use & v, instead of & ||, ∧ ∨, * +, ∪ ∩. Weird..

[soft pike]

Thank you gyus!

i get 4 on my examination

[sleek swallow]

is that good or bad

[soft pike]

is very good

;D so thank you so much gyus!

[stray reef]

@sleek swallow finfan seems to be Russian so a 4 is the second-highest grade

[sleek swallow]

Oh

ok ok that sounds good

[last timber]

well 4 is ~80-90%

[fossil pewter]

[last timber]

who pinged me

[hardy remnant]

for this question, I made a truth table

so how do i know which one is correct?

because "i do not know" means they may or may not want coffee

🤔 so if there is a possibility of a professor wanting coffee, then theyll always want coffee

[stray reef]

if prof 1 wanted coffee they would've said no but they didn't say no so prof 1 does want coffee

likewise for prof 2

prof 3, knowing this, concludes that prof 1 and 2 both want coffee, but prof 3 themself does not and as such says no

[hardy remnant]

ah ok

these professors need to be more concise then

[jaunty carbon]

I want some coffeee

[hardy remnant]

i dont drink coffee

maybe thats why the question stumped me

[dusky pond]

Anyone know how to solve this recurrence relation?

$$T(n^2) = T((n/2)^2) + 6(n/2)$$

[vital dew]

Circulation:

[dusky pond]

not so sure how i can use the master theorem here

[dusky pond]

<@&286206848099549185>

[whole shard]

i thought it requires initial value

[hasty glade]

$2n^{2}+3n+1 = (n+1)(2[n+1]-1)$

[vital dew]

AfterJack:

[hasty glade]

How would you prove that ?

[whole shard]

WYM

foil?

[hasty glade]

I need to make te left side be equal to the right side

without touching the right side

[whole shard]

oh then u dont wanna use quadratic equation?

[hasty glade]

But you will get 2(x+1)(x+1/2)

[stray reef]

no you won't

[whole shard]

(2n+1)(n+1)

[hasty glade]

What did you do ?

[whole shard]

sysmolab

[hasty glade]

But that completed the square

[whole shard]

idk what u saying

[hasty glade]

I mean

I did the Baskara formula

[whole shard]

baskara?

[hasty glade]

Sorry I m not an english speacker

[whole shard]

o ya looks good

[hasty glade]

And I get the roots -1/2 and -1

With the 2 coeficient it will be 2(x+1)(x+1/2)

[whole shard]

whats the issue

multiply 2 with (x+1/2)?

[hasty glade]

I did it...

Thanks

I would not realize

I did 2(x+1/2)

and then added +2 -2

and done

Thanks !

Any advice with this kind of exercises ?

[whole shard]

sorry idk how I helped u

[hasty glade]

You told me to use quadratic

I got the (n+1)

and then I worked the 2(n+1/2)

And arrived to the answer

[hardy remnant]

is there a difference in where i put the not in this logic?

for example, i put my not in front of the upside down A

[whole shard]

yes big diff

[native steeple]

Can anyone help me with the math of feedback loops

https://youtu.be/inVZoI1AkC8

I'm studying them in my environmental class and want to know more about the math behind them

[weary tiger]

hey did anyone have prof bamberg for discrete math?

which uni

uh bamberg taught at harvard for many years but now he's just doing with the harvard summer school and harvard extension school

@weary tiger

bruh if someone was from harvard you think they'd be in this server lmaooooooo

they too smart for here

lol woog told me there were some people who went to harvard summer school or the extension school

i myself am just a lost kid in hs lol

[faint narwhal]

there are people from harvard in here lmao

[tulip ravine]

I will save my Harvard jokes for elsewhere then 😛

Besides, someone the other day said I was wholesome, I have an image to maintain haha

[errant bear]

rent free acting like harvard is full of stephen hawkings

[hardy remnant]

its full of smart and hardworking people

🙂

[vapid light]

Is there a big brain emote

[weary tiger]

no

make one

lol

[vapid light]

I don't handle emotes here and I don't have nitro

[weary tiger]

dang

im in the boat as u

[pallid lintel]

is this formula for upper bound on ramsey numbers true because in the inductive argument from ramsey's theorem, we have r-1 vertices with a red clique or s vertices with blue clique, and we choose r-1 vertices in the red clique to attatch to another vertex to get R(r,s) with a r vertex red clique (or s vertex blue clique). I wasn't sure where the 'r+s-2' elements came from. Is it from choosing from the 'r-1 +s -v' element set, where v is the vertex we add red edges to v from the r-1 clique?

[pallid lintel]

ramsey's theorem

[hasty glade]

Could someonle explain me please Modus Tollens ?

[weary tiger]

Hey all, I got a question mathematical induction, to prove Fibonacci number of is even, for all values of n >= 0, what would that statement look like?

I wrote the statement

[obtuse lance]

look at the recurrence relation

and think about what happens when you add even and odd numbers

[weary tiger]

but once I get to induction, I cannot translate the LHS to RHS. Its not possible

[obtuse lance]

don't think about induction yet

do you see how it's true first

based off what I said

[weary tiger]

Well, even + odd would make it odd, even + even = even

[obtuse lance]

maybe list out the numbers and if they're even or odd next to it to help you reason through it

I know you just want the answer by induction but you have to actually think about the problem to discover it first and try to package it all nice and neat that into an induction argument, it doesn't come fully formed

[weary tiger]

I do see that every index divisible by 3 is even

and thats because the 2 previous index's are odd value

but how would I express that in a statement

I cant figure this out at all

I have a proof, that shows it even, but I just dont know how to write a statement that says its even

Can I just write my statement as "S(k) : F3k is even"

or do I need to express that using logic?

[hasty glade]

What are Modus Ponens, and Modus Tollens

What are they ?

[weary tiger]

What about S(k): F3k mod 2 = 0? Is that a valid statement

[rough ledge]

@hasty glade

modus ponens:
P -> Q
P
Therefore Q

Modus tolens:
P -> Q
~Q
Therefore ~P

[hasty glade]

(Q ^ (Q --> P) --> -Q ????

That is what I was given

[rough ledge]

MODUS PONES

If Socratis is a man then Socratis is a mortal
Socratis is a man
Therefore Socratis is a mortal

MODUS TOLLENS
Ig Socratis is a man then Socratis is a mortal
Socratis is not a mortal
Therefore Socratis is not a man

[hasty glade]

and (-P ^ (Q --> P) --> Q)

But those statements, they are always true in order to be a reasoning ?

Is that right ?

[rough ledge]

yes

[hasty glade]

Thanks a lot !

Do you know what this is ?

[rough ledge]

you mean which rule of inference?

[hasty glade]

Ignore the spanish

Can you identify that ? Or you might need a traslation ?

[rough ledge]

(Q ^ (Q --> P) --> -Q

they asked you what about this?

from my book

[hasty glade]

Oh I get it

They are the same notaiton

Because p --> q and p will be joint by ^

[rough ledge]

yes

(Q ^ (Q --> P) == (q --> p) I think

if you are in doubt

you can make truth tables

and see if the two are logically equivelant

[hardy remnant]

we are using the same book @rough ledge

[rough ledge]

Got an exam this wednesday

XD

Man its so hard to rememebr all that stuff

we have of chapter 1 2, 3,4 5,6,7

they should really do 1 exam per chapter

It's already a bit vague why with statement forms we only look at the critical row

[hasty glade]

I have an exam tomoroww

tomorrow

Induction, Classic Logic, Number Theory and Recurrency

I have been studying 7 hours per day...

[lyric pumice]

@hasty glade Are you majoring in math?

[hasty glade]

Software Engineering

[lyric pumice]

Oh, good.

[pallid lintel]

I got a conjecture, i think i proved it though. Conjecture: If we colour the edges of a complete graph red or blue, we guarentee existence of a monochromatic cycle of size n/2 for K_n the complete graph on n vertices

im guessing someone proved it already or im wrong

we proved that red/blue edge colouring of K6 has a monochromatic cycle of size 4 in class, i thought perhaps we can generalize an answer for all complete graphs

thoughts anyone?

[full reef]

Can someone here help me with converting generating functions in closed form to their summation form??

Or is there a better channel for this?

[stray reef]

post your problem

[full reef]

I'm wondering how my lecturer got the answer to the third question here.

I don't quite understand his process. The exponent on the denominator is tripping me up

[stray reef]

you can take the power series of $\frac{1/2}{1-z}$ (which is just a geometric series with ratio $z$ and first term $1/2$) and then take its derivative to get the power series for $\frac{1/2}{(1-z)^2}$

[vital dew]

Ann:

[full reef]

Okay, I get that. So basically the proposition we have to work with is: [ \frac{1}{1-\alpha z}=\sum_{i=0}^{\infty}\alpha^i z^i,] and we are asked to find the value of $\alpha$ and compute some of the terms in the series. The bit I am confused with is how he got $\alpha=\frac{i+1}{2}$...

[vital dew]

user450-425*10^-9:

[stray reef]

he did not

$\frac{1/2}{1-z} = \frac12 \times \frac{1}{1-1z} = \frac12 \sum_{i=0}^{\infty} 1^i z^i = \sum_{i=0}^{\infty} \frac12 z^i$

[vital dew]

Ann:

[stray reef]

this is what i said

do you understand this

[full reef]

Yep, I understand that

[stray reef]

now differentiate both sides with respect to z

$\frac{1/2}{(1-z)^2} = \sum_{i=1}^{\infty} \frac12 i z^{i-1}$

[vital dew]

Ann:

[stray reef]

note that this is no longer a geometric series

[full reef]

Ah, okay

[robust mango]

Is $P \land Q \land R \land S \equiv (P \land Q) \land (R \land S)?$

[vital dew]

Sup?:

[stray reef]

yes

[robust mango]

Thank you.

Another question: Suppose the conclusion of an argument is a tautology. What can you conclude about the validity of the argument? What if the conclusion is a contradiction? What if one of the premises is either a tautology or a contradiction?

For the first, I think that the argument is not valid because the premises could be true or false. For the argument to be valid, we need the premises to be true with the conclusion being true as well. For the second, I think the same because the premises could be true and the conclusion is always false which means the argument isn't valid. I'm not sure about the third.

actually I searched online and found a few explanations. but if anyone wants to have a go, you're welcome!

[stray reef]

that's not what validity means

[robust mango]

Yeah I was confused Im reading about it now

[hardy remnant]

its been 3 weeks and im still on chapter 1 😦

how did the q disappear?

i dont see any steps here

[surreal bobcat]

hello, is there a tool that allows me to draw a graph and it would check it's properties (for example if it has Eulerian path, Hamiltonian path, tree properties etc.)

ah, Wolfram has it actually

[hardy remnant]

please tell me the first chapter is the hardest part of discrete

i am not having a good time

[gleaming zephyr]

what are you taking

[rough ledge]

Question about set theory is a empty set a proper subset of any other set?

or

is a empty set a proper subset of any other set?

[vapid light]

I think it's just a subset

[rough ledge]

Ok thanks :)

[vapid light]

Usually proper subsets have a cardinality between 0 and the whole set, both exclusive

Unless your textbook has it defined differently

[rough ledge]

it says:

The empty set, written as { }, is a subset of each set A. The empty collection is always a proper subset, except for itself.

It is kinda confusing me

[vapid light]

Ok, then by your book, if a set is not the empty set, the {} is a proper subset

proper subsets are subsets with a cardinality smaller than the original set

[rough ledge]

yes

[vapid light]

Since {} and {} have the same cardinality, {} is a subset but not a proper subset of {}

[vapid light]

Yep

[rough ledge]

there need to be atleast 1 different item in a proper subset

Yes the book confused me a bit

The empty set, written as { }, is a subset of each set A.

because they say this first

next they say:

The empty collection is always a proper subset, except for itself.

[vapid light]

Subsets can't have elements different from the original

Then it stops being a subset

[hasty glade]

Guys consider $a_{n}= 6+a_{n-2}$

[vital dew]

AfterJack:

[hasty glade]

The order of this equation is 2 or 1 ?

[keen python]

2

[still jetty]

could someone help me out with this one;

In how many ways can a boat crew of eight women be arranged if three of the women can only row on the bow side and two others can only row on the stroke side?

[pallid lintel]

do we have to make sure four are on either side because that's how rowing normally works, heh

[still jetty]

aa i just worked it out. yes you have to assume its 4 on either side to get the answer

thats where i was most confused ;;

[pallid lintel]

cool. what is the answer

[still jetty]

4 * 3 * 2 * 4 * 3 * 3!

= 1728

[pallid lintel]

oh, we are arranging seating arrangements on either side as well?

[still jetty]

i dont quite get what you mean by arranging seating arrangements

[pallid lintel]

i just mean that we are ordering each subset of 4 on each side. They row from different positions

like {3,4,2,1} can be a way of seat each rower, {4,3,2,1} is another

[still jetty]

no, theres no order involved; as in yes there is multiple variations such as 1234 4321 2341 etc.

basically we know that 3 of the women must be on the bow side, and since we have assumed there are 4 seats on either side the sub question this situation poses is how many ways can 3 women be arranged in 4 seats

= 4 * 3 * 2 ways

now for the other two women who can only row on the stroke side; how many ways can these 2 women be arranged in 4 seats. = 4 * 3 ways.

so for the remaining 3 women there are 3 remaining seats; so they can be arranged 3! ways. therefore the total number of ways the women can be arranged is; 4 * 3 * 2 * 4 * 3 * 3! = 1728 ways

[languid flint]

is there a definite method to find the chromatic polynomial of a graph?

and also it's chromatic number

[tulip ravine]

Well, you can certainly find the chromatic number by exhaustion. What you probably want is an efficient way to find the chromatic number, but even finding a 3-coloring of a graph known to have chromatic number 3 is thought to be cryptographically hard.

[languid flint]

I am stuck on finding a chromatic polynomial for this one. Any idea?

[tulip ravine]

you'll want to use the deletion contraction algorithm to build up that graph from the chromatic polynomial of graphs you know.

In particular, you know the chromatic polynomial of a triangle, so you know the chromatic polynomial of two triangles, so one application of the recursion will give you the chromatic number of this graph

[languid flint]

in the deletion contraction, I get stuck at the P(G/uv, lambda) part

[tulip ravine]

So, you're looking for the chromatic polynomial of the bowtie graph, basically?

Hint: you can compute that directly.

[languid flint]

yea

um, how?

[tulip ravine]

That is to say, just answer the question "how many colorings does this graph have?"

(Use the multiplication principle)

[languid flint]

it should be 3 but how do I arrive at that?

[tulip ravine]

the answer should be a polynomial, not a number

So this is the contraction, right?

[languid flint]

yes

but I don't have any clue on how to begin

[tulip ravine]

I want to know how many ways I can color this in n colors

so first, choose the color of the middle vertex.

I can do that in n ways

Now the top left vertex I can do in n-1 ways

and the bottom left vertex in n-2 ways

Do you see where that is coming from?

[languid flint]

it sort of makes sense but I am not entirely sure, what will it be for top right and bottom right?

[tulip ravine]

I'm going to leave that for you to figrue out, since once you've understood that, you're done

[languid flint]

can they be top right: n-1 and bottom right: n-2 ?

[tulip ravine]

perfect

[languid flint]

and with this, how do I arrive at the polynomial, will it be just the product of those terms?

[tulip ravine]

Yes, that's what the multiplication principle says, if you are counting something arrived at by a sequence of choices, you multiply the number of options at each step in the sequence

[languid flint]

oh

and on the wikipedia page of bowtie graph, there is a mention of "characteristic" polynomial, is it the same as chromatic polynomial?

The characteristic polynomial of the butterfly graph is $$\displaystyle -(x-1)(x+1)^{2}(x^{2}-x-4)$$

[vital dew]

arora:

[tulip ravine]

No, the characteristic polynomial is the characteristic polynomial of the incidence matrix

[languid flint]

oh ok, thanks a lot 😄

after a bit of research, that graph in question appears to be a barbell graph with n=3. It's interesting that there is a unique name for so many graphs.

[prisma arch]

Can someone help me understand how the 16 comes about?

[weary tiger]

2^4

@prisma arch

[prisma arch]

hmm so they do 2^4 is that on the (2/3) part?

what about the /3 part?

[weary tiger]

yes

it becomes 3^4

[prisma arch]

(1/3)^4?

ahh ok you drop it and it becomes 3^4

[weary tiger]

its (1/3)^3, not (1/3)^4

[prisma arch]

right

so can you solve that same thing by just multiplying across without dropping anything using a calc?

[weary tiger]

idk what u mean

[prisma arch]

like just doing 35*(2/3)^4*(1/3)^4

straight up just putting that into a calc

[weary tiger]

yah

[prisma arch]

Its because I am using this as an example for another problem I have and that one doesnt come out to convenient fractions

[weary tiger]

k

[prisma arch]

so for example for my problem I am working on it comes to 0.32 so is that the probability or does it still need to be converted to a percentage?

[weary tiger]

keep it as a decimal

bc probability is always between 0 and 1

[prisma arch]

oh I see I thought I had read that somewhere but I was like damn maybe not

[weary tiger]

i mean i guess if the question says put it in a percentage then u have to put it in one

but it would be a decimal otherwise

[prisma arch]

Sounds good

[prisma arch]

Is there a way to do this faster than just doing the sums for each different N?

nvm im pretty sure this boils down to 1^n

[stray reef]

that it does

[thorny willow]

i need some help with (g). The hint says prove by cases; I tried but I don't see how considering cases where R and S are not boring is going to lead to desired result.

[stray reef]

what's $R \cdot S$?

[vital dew]

Ann:

[stray reef]

@thorny willow

[thorny willow]

Sorry should have mentioned that earlier.
It's R concatenated with S.

[stray reef]

so... {rs | r ∈ R, s ∈ S}?

[thorny willow]

Yeah

[stray reef]

hm

[thorny willow]

Intuitively, I can understand. If R and S have a finite number of all-0 words, then R.S would have a finite number of all-0 words.
I guess the difficulty would be proving (R.S)' is also 0-finite, but I'm not sure how proof by cases might help.

[languid flint]

um, what does 0 star mean in that?

[stray reef]

0* means {0, 00, 000, 0000, ....}

ie the set of all words that are just a string of zeros

[languid flint]

oh

@thorny willow why do you need to prove (R.S)' is also 0 finite?

there are three cases,
both R and S are 0 finite,
neither of them is 0 finite,
and only of them is 0 finite,
maybe you can verify them individually.

[thorny willow]

Oh, I see how cases work now.
Says either S or S' is 0-finite.
So if S is not 0-finite then I have to show S' is 0-finite

[spare jolt]

So I'm trying to find the x^2 coefficient for the taylor series expansion (at 0) for:

$$\frac{1}{\left(1-x\right)^4\left(1+x\right)^3}$$

[vital dew]

Soup:

[spare jolt]

I thought I should use partial fractions, but it ends up being a massive mess

Differentiating it also turns out to be a massive mess

Is there any nicer way I can find x^2 coefficient of this?

[tulip ravine]

you know the taylor series of 1/(1-x)^4 and 1/(1+x)^3 so you can multiply them together

[spare jolt]

Oh lol, I didn't think about that.

Thanks heaps

[tulip ravine]

haha I'm definitely not saying it will be pretty, but it will be better than the alternatives (-:

[weary tiger]

hi

trying to get this

and i've written it like that, but I think I went wrong somewhere trying to find all the ways to make z^57 because I got a way bigger number than what the question has

this is giving me a mental breakdown i don't know why

DONT WORRY I GOT IT

[whole shard]

U got it rusty

[dark stirrup]

Hi everyone, I'm trying to solve this problem and I'm not getting any idea. Can someone help me start?

[stray reef]

his/her

[tall depot]

if there is a bijective function between AxC and BxD, does it mean that there also must be one between A and B and C and D?

[stray reef]

did you mean "between A and B and between C and D"

because if so, then no

take A = {1,2,3,4}, B = {1,2,3,4,5,6}, C = {1,2,3}, D = {1,2}

|A × C| = |B × D| = 12 yet there is no bijection A -> B nor is there a bijection C -> D

[tall depot]

yes, and ok got it thanks. Just to confirm I got it right... if we additionaly know there is a Bijection between A and B, then there must be one between C and D as well, correct?

[stray reef]

no. take A = B = N, C = {1,2,3}, D = {1,2}

[tall depot]

huum

basically I am trying to figure out if A~B and AxC~BxD then if it must be the case that C~D

[stray reef]

i just gave you a counterexample

[tall depot]

yep

thanks a lot!

[languid flint]

@dark stirrup if we see it as a tree, it will be like 1 root -> 3 children and each of those 3 children having 3 more children and so on.

[languid flint]

they said "we are not going into details how this is decided" but isn't that detail important?

I am not sure but could the RR be

$$ T(n) = 3 \cdot T(\frac{n}{3}) + O(1) $$

[vital dew]

arora:

[rain stone]

@tall depot althouh I'm fairly certain that if you have that A, B, C and D are finite and nonempty, then it holds. Cardinality of the cartesian product is product of the cardinalities for finite, nonempty sets. if you have that
|A| * |B| = |C| * |D|
and
|A| = |C|

Then you can divide both sides by |A|, provided that |A| is both finite and nonzero

Ann, please correct me if I'm wrong though

[stray reef]

i mean yea if they're finite and nonempty then of course it holds

[weary tiger]

if you have a standard deck of 26 red and 26 black cards and you shuffle it

what is the probability that the top card is the same color as the bottom card

[vestal moth]

tree diagram probably

[weary tiger]

oh no

[vestal moth]

top card can be red or black, either with probability 0.5
bottom card can be red or black, either with probability 0.5

so:
red-red (0.25)
red-black (0.25)
black-red (0.25)
black-black (0.25) , i think

so probabilty same colour should just be 1/2

[weary tiger]

nope

[vestal moth]

hm

[weary tiger]

i know that is incorrect

but i don't know what is correct

[vestal moth]

ohh because

when u pick one red

then you have 25/26 red cards

not 0.5

Yep that fixes my mistake

[weary tiger]

A) Secure key distribution is difficult in asymmetric encryption algorithms.
B) Symmetric encryption is not scalable.
C) In symmetric encryption, the security of the system depends on the privacy of the key.
D) Asymmetric encryption offers the possibility of e-signature.
E) Symmetric encryption algorithms are faster than asymmetric encryption algorithms.

which is wrong?

[vestal moth]

does it make sense polynomial

[weary tiger]

idk

E is correct.

[vestal moth]

if you pick top card = red, then theres only 25 reds so probability red-red = (1/2) times (25/51)

pick top-card = red, then 26 blacks out of 51 cards

red-black = (1/2)(26/51)

black-black is (1/2)(25/51)

so the answer is 25/51

[weary tiger]

how do you get the final answer though

[vestal moth]

Pr(red-red) + Pr(black-black)

[weary tiger]

so... 25/51 + 25/51

98%

doesn't seem right lol

@vestal moth ?

[vestal moth]

no lol

Pr(red-red) $= \frac12\times\frac{25}{51}$ \
Pr(black-black) $= \frac12\times\frac{25}{51}$

[vital dew]

L'Âne 🍐:

[weary tiger]

and then what

[vestal moth]

Pr(red-red) + Pr(black-black)
@vestal moth

[weary tiger]

so (1/2 * 25/51) *2 = 25/51?

[vestal moth]

These are the only two ways u can have them be the same colour no??

yes

correct

by the way it's time

1/2 times 25/51

not plus

(1/2 * 25/51) * 2 = 25/51

because 1/2 * 2 = 1

[weary tiger]

i know

i typod sorry

on that part

(otherwise it wouldn't be equal to 25/51)

[grim grail]

Which of the following is the runtime of an algorithm given by T(n)-6T(n-1) + 9T(n-2) = 0?

A) T(n)=c1 *3^n+c2 * 3^n, T(n)=O(3^n)
B) T(n)=ct *3^n+c2 * 3^n, T(n)=O(n3^n)
C) T(n)=ct *3^n+c2 n 3^n, Tn)=O(n3^n)
D) T(n)=c1 * 3^n+c2 * 3^n, T(n)=O(3^n)
E)None

[sullen hazel]

Can anyone help me with this?

[gleaming zephyr]

use induction

[sullen hazel]

@gleaming zephyr yeah

[gleaming zephyr]

assume its true for all k >= 3 uptill some i

prove it works for k+1

u need all the condditions

u need strong here

[sullen hazel]

my proof is above

not complete

but are we sorta good

[gleaming zephyr]

yes

yea

i think

keep going

[sullen hazel]

so now for the inductive step

n = k+ 2

?

[gleaming zephyr]

n=k+1

assume its true for all k less than or equal

show its true for k+1

[sullen hazel]

hmm just to clarify because i showed n = 3 and n = 4 are true in step 1

[gleaming zephyr]

why

n=3 is enough

[sullen hazel]

is that not strong induction

[gleaming zephyr]

weak induction : show base case --> assume its true for p(k) --> show its true for p(k+1)

strong induction same but you also assume all values before k

[sullen hazel]

ooh

thank you

"before k"

[gleaming zephyr]

if p is ur proposition

[sullen hazel]

ok, so basically im just over complicating this proof than i should have

thank you

[gleaming zephyr]

u assume p(1) p(2) p(3) .... p(k) --> show its true for p(k+1)

thats after showing base case

ofc

[sullen hazel]

now for the inductive step, after plugging k+1 for every n shown

we now expand the fibonacci to the two preceding terms here

right

[gleaming zephyr]

yes

what

yea

and then use ur assumption

cool right?

[sullen hazel]

here is my step 3

i only expanded, now how do i use my assumption here, it's pretty hard to plug in unless i mislooked

[gleaming zephyr]

switch

a+b = b+a

[sullen hazel]

can you elaborate

please

[gleaming zephyr]

whats your assumption

can u write it out

here

[sullen hazel]

no but i can take a pic

[gleaming zephyr]

,rotate

[gleaming zephyr]

okay

what do you have

( that is true for all values less than or equal to k )

so its true for f_k-1 + f_k-2 + .... = 2^(k-2)

and so on

[sullen hazel]

did i even need to expand the fibonacci

[gleaming zephyr]

idk

[sullen hazel]

ok wait wait wait

how do i explain what you just said

i'm having an issue using the assumption that i showed

[gleaming zephyr]

what was your assumption

[sullen hazel]

and applying it here

[gleaming zephyr]

no

i mean

whats k in your assumptioln

what ks make your assumption hold

[sullen hazel]

n = k + 1

[gleaming zephyr]

no?

thats not your assumption

thats what you want to show using your assumption

[sullen hazel]

n = k >/3

oops

[gleaming zephyr]

yea

so

[sullen hazel]

mhm

[gleaming zephyr]

is k-1 in this interval

or

like

in the 'set of all ks that make this true'?

[sullen hazel]

is the k-1 you're referring to is the one i wrote in step 3?

[gleaming zephyr]

no im just asking

does your assumption

include the case n=k-1

if yes

think how you can use that

[sullen hazel]

idk? i only wrote n = k >/ 3

[gleaming zephyr]

strong induction assumes

[sullen hazel]

so then yes

[gleaming zephyr]

that this prop holds for all values up to or equal k

[sullen hazel]

since we are talking about strong induction

[gleaming zephyr]

k-1 is less than k

yea

[sullen hazel]

yea

[gleaming zephyr]

so thats why we need strong

so now can u try to do it

?

[sullen hazel]

so for step 2, plug in n = k - 1

after n = k >/3

[gleaming zephyr]

what does

n= k>/3 mean

greater than or equal?

[sullen hazel]

ye

[gleaming zephyr]

okay

whats step 2

anyways

recap

you prove base case

assume the proposition holds for all values up to some k

=3

show its true for k+1

[sullen hazel]

step 1 - basis step
step 2 - assumption
step 3 - n = k + 1

[gleaming zephyr]

yes

now the hint was just recognizing

that it works for f_k-1

it being the assumption

that is : f_k-1 + f_k-2 + f_k-3 +2f_k-4 + ..... = 2^(k-2)

i dont think this holds for any random sequence

so i think yea ur going to need

to use fibonnaci stuff

eventually

[sullen hazel]

wait wait

please slow down

i'm trying to work this problem and there's so much information, and what i tried asking you was in step 2 (assumption step)

after i write n = k >/3 where i plug in k for ever n there is in the original statement

after this part of this step, i want to plug in n = k - 1 for every n in step 2

[gleaming zephyr]

okay go ahead

whats stopping you

[sullen hazel]

it seems like right there it's not necessary?

[gleaming zephyr]

thats what goes to the mind

once you see this

https://media.discordapp.net/attachments/496785905474994186/722575362294415460/image0.jpg?width=477&height=636

just make it look like the assumption

thats it

[sullen hazel]

ok there, it starts with "and for n = k - 1..."

[weary tiger]

aₙ-6aₙ₋₁+12aₙ₋₂-8aₙ₋₃=0

How to solve this recurrence 🤨

[sullen hazel]

@gleaming zephyr it was helpful that i did that

i see it now

[gleaming zephyr]

cool

anything else

[sullen hazel]

nope im good

it was my last my problem

[gleaming zephyr]

cool

[weary tiger]

aₙ-6aₙ₋₁+12aₙ₋₂-8aₙ₋₃=0
@weary tiger is that everything you know about this recurrence?

@weary tiger recurrence relation

Yep

no value for any a_n?

*no known value

@weary tiger https://cdn.discordapp.com/attachments/722502790173425792/722505500066840657/IMG-20200613-WA0086.png

Here is the question

Is it a wrong question? @weary tiger

[weary tiger]

no, it's good afaik

answer B is correct, you need to find characteristic polynomial of this relation, then solve for roots

in this case characteristic polynomial is x^3-6x^2+12x-8

which is equal to (x-2)^3

[spare jolt]

1/16(1 + i)^8
Solve (1 +i)^8
(1 + i)^8 = ( (1 + i)^2 )^4
(1 + i)(1 + i) = 1 + i + i - 1
(1 + i)^2 = 2i
(1 + i)^8 = ( 2i )^4 = 2^4 * i^4
(1 + i)^8 = 16 * 1
(1 + i)^8 = 16
Put back in
1/16(1 + i)^8 = 1/16 * 16 = 1
1/16(1 + i)^8 = 1 + 0i
1/16(1 + i)^8 = (cos(0) + isin(0))

Is this correct?

It feels strange that 1/16(1 + i)^8, such a large looking number turns into a 1.

[stray reef]

yes, you are correct.

$\frac{1}{16} (1+i)^8$ does indeed simplify to 1.

[vital dew]

Ann:

[stray reef]

one could, if desired, write it as $\paren{\frac{1+i}{\sqrt{2}}}^8$, and notice that $\frac{1+i}{\sqrt{2}} = e^{i\pi/4}$

[vital dew]

Ann:

[spare jolt]

Ah right, thats' a much nicer way! Thanks

[runic cedar]

is there an easy, hand way of calculating large modulo values like 11^13 mod 782077 ?

[stray reef]

repeated squaring

[runic cedar]

oh, cool. thanks

[dull magnet]

hey I just had a question about set notation, whats the point in having a "proper subset notation (the sideways u with no line underneath) when you can just use the normal subset notation (the sideways u with a line unbderneath)? I understand that the proper subset notation means "every element in 'a' is also an elemnt of 'b', but not every element in 'b' is in 'a' " so its very strict while the a normal subset means "every elemnt in 'a' is also in 'b' and every element in 'b' can also be an element in 'a'". They only differ with one little piece of information, are proper subsets even helpful? why not just use normal subsets, that allows us to keep a set within a set while allowing it to also contain the same elements as the other set?

[stray reef]

sometimes you really \textbf{do} care about strict vs nonstrict inclusion, i.e. sometimes it matters that $A \subseteq B$ but $B \nsubseteq A$

[vital dew]

Ann:

[dull magnet]

ahhh

[wanton current]

what does it mean by "how many boolean functions" ?

[dull magnet]

so in times like this it would matter

but if it doesnt matter

[stray reef]

ie a proof may rely on taking an element from B \ A, which is impossible if A = B

[dull magnet]

ahhh

i see

[stray reef]

@wanton current you are asked how many functions exist from ${0,1}^3$ to ${0, 1}$

[vital dew]

Ann:

[stray reef]

a boolean function is a function with values in {0,1}

or {FALSE, TRUE} as things may be

[wanton current]

sure, so a single boolean function means it only outputs true or false?

[stray reef]

??

[wanton current]

yea this is what i dont really get lol

[stray reef]

a boolean function is a function with codomain {0,1}

don't overthink it

[wanton current]

agree. but what does the text mean when it says there are 2^8 boolean functions?

there are 2^8 functions with that codomain {0,1} ?

what differentiates them?

[stray reef]

what differentiates them is their rules lmao

for example, one of the 2^8 functions from {0,1}^3 to {0,1} is the function that maps 001, 010, 011 and 100 to 0 and the rest to 1

another would be the constant 0 function

another still would be the constant 1 function

yet another would be the function that returns the first bit of the input but flipped

and there are 252 more functions from {0,1}^3 to {0,1} which i have not mentioned

[wanton current]

ahh so in your example regardless of input there is one boolean function that maps to only one? (constant 1 function)

[stray reef]

wrong order

there is a boolean function which, regardless of its input, maps to 1

yknow. like a constant function does.

it's not like it's an unfathomable beast

[wanton current]

ah i am getting it haha thank you

[stray reef]

a function f: {0,1}^3 -> {0,1} is identified only by f(000), f(001), f(010), f(011), f(100), f(101), f(110) and f(111)

there are 2 options for each of these 8 choices

hence 2^8 is the count of all possible functions from {0,1}^3 to {0,1}

[wanton current]

i intuitvely get why it's base 2 in the 2^8 (true or false duh), but what exactly is the 2? can you sort all of those boolean functions into 2 groups?

[stray reef]

no

the 2 is

the number of elements in {0,1}

since yknow

THERE'S TWO OF EM

[wanton current]

im kinda dumb

thx

[stray reef]

so f(000) can be either 0 or 1

f(000) has two options for what it can be

[wanton current]

this text is gonna be such a struggle

[stray reef]

as does f(001)

[wanton current]

hahahahahahah

[stray reef]

as does f(010)

[wanton current]

thank you so much

[echo rivet]

Is union of posets is poset?

[honest barn]

You need to define a relation on it

ai priori the union of sets is just that, a set, and you can construct a poset on any arbitrary set, so the question as stated doesn't really make sense

If you take the relation where you kind of like, piecewise do the relation on each part, then it becomes more interesting

I want to say that it isn't

[echo rivet]

alright that makes sense

[honest barn]

I guess I'll expand on what I meant by that though haha

[echo rivet]

the question was "Let A and B is posets on set S, is A U B a posets on set S"

[honest barn]

Ohhhhhh

A union of the relations themselves

Sorry, people often say poset to like, refer to the set and relation together

I didn't realize it was talking about considering the relation as a set and then taking the union

[last timber]

the question was "Let A and B is posets on set S, is A U B is posets on set S"
It is

since it preserves all the properties of A, B

i.e. reflexivity

transitivity

and antisymmetry

[honest barn]

Wait, I don't see how that's true. Couldn't you have x <= y via A with y not equal to x, and then y <= x via B

Then in A U B you have both x <= y and y <= x but the two aren't equal

Take like inclusion on P(X) and then the reverse one where A <= B when B is a subset of A

[last timber]

actually, we need to have more info about nature of relation ye

like if relation is the same for both then it would be poset

[honest barn]

I mean if the relation is the same for both then A = B right?

At the very least it'll still be a preorder

I think the only way it can fail is with antisymmetry

[last timber]

like if we have sets Q-Z and Z with usual < relation then it would be a poset

[honest barn]

Actually, it still isn't even transitive I think

I think you can have x <= y in A

and y <= z in B

[last timber]

yes

oh lol yes

[honest barn]

if you don't have x <= z in A or B then it won't be transitive

[last timber]

my proposition was true if A and B are disjoint

[honest barn]

Literally the only thing preserved is reflexivity

[echo rivet]

Alright, crystal clear

Thank you mates

[errant bear]

you're welcome 👍

[weary tiger]

Hello guys. Is "\exists a \in Z , \forall x \in Z , a x = x" true?

I try to prove it but I can't that's why I'm asking

[loud copper]

just take a = 1

[languid flint]

Is there a way to find the maximum number of vertices in an n-ary tree of height h?

[stray reef]

surely the node count is maximized if every node has as many children as possible

[languid flint]

indeed

but is there a generalized formula for it?

[last timber]

what is n-ary tree?

[languid flint]

a rooted tree in which each vertex has atmost n children

[stray reef]

well

in a complete n-ary tree the node counts per layer follow a geometric progression

[last timber]

yep

like in n-ary tree of height h there is at most n^h leaves

[languid flint]

oh ok

[last timber]

you canjust sum up

[languid flint]

it appears that maximum number of vertices is $$ n^{h+1} -1 $$

[vital dew]

arora:

[last timber]

or
there is theorem that
full m-ary tree (which has obviously the maximal number of vertices) with l leaves has $n=\frac{ml-1}{m-1}$ vertices

[vital dew]

Commander Vimes:

[stray reef]

$\frac{n^{h+1} - 1}{n - 1}$ surely

[vital dew]

Ann:

[languid flint]

oops right, I tried to figure out the formula from the binary tree properties 😅

[last timber]

oops right, I tried to figure out the formula from the binary tree properties 😅
well

actually this formula follows from these properties

like
look
i have tree
a
b c
d e f
g h i j

like i firstly consider level 0 and get 2^0 leaves

then at lever 1 there are 2^1 leaves and 2^0+2^1 vertices

so just following the same logic i get 2^0+...2^h vertices

which is geometric progression and formula is well known

i used binary tree here

but it could be any full m-ary tree

[languid flint]

aha, right

thanks 🙂

[topaz sky]

hi can someone explain me this ?

[last timber]

ok so in first line it is just multiplicativity

is it clear?

[stray reef]

are these lagrange symbols

[last timber]

i suppose

[languid flint]

*legendre symbol?

[heavy crescent]

I imagine most people here are familiar with this proof: Prove that √2 is irrational by giving a proof by contradiction.

Does that mean √2 can be express as a/b with common factors?

[topaz sky]

yes it is legendre symbol

but I don't get the 3rd line with 20/37

[stray reef]

sdetdgtjflkFHJ

fuck

forgive me i only have one active braincell right now

the rest have been eradicated by the heat

[last timber]

but I don't get the 3rd line with 20/37
131 = 111+20

and 111 = 37*3

[languid flint]

$$ if a ≡ b (mod p), then
{\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).} $$

[last timber]

$$

before and after math

$\text{math} x+yt+z=0$ usual text

[weary tiger]

I imagine most people here are familiar with this proof: Prove that √2 is irrational by giving a proof by contradiction.

Does that mean √2 can be express as a/b with common factors?
gcd(a,b)=1

[vital dew]

Commander Vimes:

[last timber]

I imagine most people here are familiar with this proof: Prove that √2 is irrational by giving a proof by contradiction.

Does that mean √2 can be express as a/b with common factors?
suppose sqrt(2) is rational and can be expressed as p/q with no common factors

[vital dew]

arora:

[languid flint]

interesting.

[topaz sky]

and 111 = 37*3
@last timber ok so where does it go ?

[topaz sky]

i don't understand the formula, what is it if we replace ?

[last timber]

$a = kp + b$ for some integer k $\implies \left( \frac{a}{p} \right) = \left( \frac{b}{p} \right)$

[vital dew]

Commander Vimes:

[languid flint]

131 = 3*37 + 20 i.e. 131 ≡ 20 (mod 37)

[topaz sky]

ok thank you

and at the final line, why do we got -1.1.-1 ?

[last timber]

because of the definition for values of legendre

[languid flint]

quadratic residue gives 1

else -1

yea

[vital dew]

arora:

[topaz sky]

so 131 - 2 = 129 = -1 ?

[languid flint]

oh wait no, I am not sure, I have deleted the previous messages to not cause any confusion for you.

[topaz sky]

its alright, math always confused me

[languid flint]

if the order of x is 18, what will be the order of

$$ x^{-1} \quad and \quad x^{-4} $$

[vital dew]

arora:

[last timber]

If order of x is n

[languid flint]

then

[last timber]

then order of x^a is n/(n, a)

where () denoted gcd

and order of x^-a = order of x^a

[languid flint]

oh ok, and is there a webpage on it anywhere?

I cant seem to find it on google

long live my google fu

[last timber]

https://math.stackexchange.com/questions/77314/order-of-cyclic-subgroups

for example

or just textbooks

[languid flint]

what's a good textbook on this topic?

group theory and this stuff

[last timber]

I am now doing it by Dummit and Foote Abstract Algebra

but many do not like it

Gallian is good, as I looked

Artin is nice

[languid flint]

ahaan, thanks

[honest barn]

I think this should be in the logic chat?

Rather than discrete math

[thorny willow]

whoops, I thought logic was in discrete math

I'll move over

[languid flint]

Set C = {a + ib : a, b ∈ R, where a,b both may zero also} forms a group under multiplication

Is it false?

[sour arrow]

R always includes 0 haha

[stray reef]

where a,b both may zero also
this is extraneous

[sour arrow]

Well, let's go through the axioms. You can usually assume associative for a "regular" multiplication

Is there an identity? What is it?

[stray reef]

but yes, your set includes 0 (or 0+0i, if you refuse to identify {x+0i | x ∈ R} with R itself), and this may end up being relevant

[languid flint]

identity is (1 + 0i) but there exists no inverse so it doesn't form a group, right?

[stray reef]

it's specifically 0 that doesn't have an inverse, yes

[languid flint]

ah right

[languid flint]

How can I find the number of hamiltonian cycles in these two graphs?

I tried to, but I can't see even 1

argh, why do things start making sense after posting it here

is there any method other than searching exhaustively

[tulip ravine]

to begin with, I would bold the edges taht must be part of any Hamiltonian path

[pallid lintel]

its quite easy to see one, your probably misreading the definition? A hamiltonian cycle uses every vertex in G once (except for first and last). So find a cycle that uses the 4 vertices in G1 and the 4 vertices in G2

[tulip ravine]

I admit I totally misinterpreted the graph on the left the first time I saw this

[pallid lintel]

finding a general method for hamiltonian cycle count is an interesting problem though

yeah i think just look at every vertex and it's degree when your trying to make a hamiltonian cycle, when you come across those parrallel edges, that's a two element subset.. so that doubles the different ways we get back to the original vertex to get our hamiltonian cycle

[hardy remnant]

how do you find this? the only thing in my book regarding this is just a small section

this is literally all it says

and idk how you read 1010101010

[sour arrow]

Arrange them like so:
101 1110
010 0001

All operators start with the rightmost numbers, in this case that's 0 and 1.

If both of these two numbers are 1, then the AND operator returns 1. Otherwise it returns 0. So, the rightmost number will be 0

[hardy remnant]

ooh ok i get it

thank you

[sour arrow]

Cool cool! Feel free to ask if you need any more help with it

[tame gale]

We need to demonstrate that the expression given is odd for all natural numbers.

[sour arrow]

Want to use induction?

[tame gale]

ye

[sour arrow]

What's the base case here?

[tame gale]

any method i guess

[obtuse lance]

I'd avoid induction tbh

[honest barn]

Like do cases on n even or odd

n^2 - n is even when n is even

Even when it’s odd

So n^2 - n + 41 is odd

[sour arrow]

Reduction mod 2 works, since n² = n, the equation becomes 1 and therefore is always odd

[honest barn]

Yeah, but like

Even that seems more than you need haha

[sour arrow]

It's more powerful than necessary yeah

[honest barn]

There’s really no reason to even bring in mod 2 formally haha

[tame gale]

how can i express all that?

@sour arrow

[honest barn]

I mean you can just do cases

If n is even then both n and n^2 are even

Because the product of even numbers is even

If n is odd

Then n and n^2 are both odd

Since product of odd is still odd

Then the sum or difference of two even numbers, or of two odd numbers is even

So n^2 - n is always even

Then n^2 - n + 41 is odd since even + odd is odd

[urban olive]

So n^2 - n is always even
@honest barn so basically replace n with 2k and 2k + 1 ?

It would be a case for the odd and the even then

[honest barn]

Yah but they reduce to the same thing

And yeah if you want to do it that way

But I don’t think you should have to go that far, that seems overkill to me imo

[urban olive]

Alright thx for the input, the teacher like overkill things lmao

👍

[weary tiger]

what's overkill about that?

[honest barn]

Just, you can make the statement purely in terms of products of even being even and such

Formally considering n as being even by writing it as 2k or odd as 2k + 1 seems like it’s more than you really should have to do

[weary tiger]

writing out the case work explicitly is probably not overkill in a class that would ask a question of this difficulty

it's a pretty obvious problem to anyone who has done some proofs with even and odd numbers but I don't think it's a bad idea if not

like, if he asks for confirmation that that's how one would write it explicitly, then he should probably do it at least once

I will save it for #math-pedagogy next time

[honest barn]

I guess that’s fair

I mean that’s a good point

Recognizing the level of depth that’s appropriate is important

[weary tiger]

tbh I did the same thing in reply to someone’s problem when I shouldn’t have a few days ago so that’s the only reason it was on my mind

[errant bear]

you can just factor to n(n-1) which is clearly even for all n if you dont want to do the cases

[languid flint]

is there a sequence with generating function

$$ \frac {1}{z} $$

[vital dew]

arora:

[languid flint]

it seems like an odd one, maybe I messed up somewhere else?

[stray reef]

1/z has a singularity at 0

[languid flint]

I am trying to solve this recurrence relation using generating function:

$$ S(k) - 2 S(k-1) + S(k-2) = 1 $$

[vital dew]

arora:

[last timber]

well

it can be solved withoud generating function

[languid flint]

hehe, the question explicitly mentions to use generating function

and I hate don't like it very much

it feels like cutting a cake with a sword

[last timber]

well, i have to recall this topic but what i suggest is to solve first characteristic equation of homogeneous recurrence and then to solve nonhomogeneous @languid flint

why should it be A

simple graph is graph with no loops

and with no multiple edges

it has nothing to do with connectivity

[languid flint]

well, i have to recall this topic but what i suggest is to solve first characteristic equation of homogeneous recurrence and then to solve nonhomogeneous @languid flint
@last timber oh yea I could try that, to cross check the answers.

[last timber]

actually just first link in google by the request "generating function for recurrences" does exactly this

[languid flint]

it's supposed to be done differently using generating functions, not using the characteristic equation

something like

multiplying everywhere with z^n and taking summation from 2 to infinity

[last timber]

well, i can assure that $\G(x) = a_0+a_1x+\ldots+a_nx^n+\ldots$

[vital dew]

Commander Vimes:

[last timber]

where $a_i = S(i)$

[vital dew]

Commander Vimes:

[last timber]

but i've forgotten this part of recurrences

[languid flint]

$$ \sum_{k=2}^{\infty}s(k)\cdot z^k - 2 \cdot\sum_{k=2}^{\infty} s(k-1) \cdot z^k + \sum_{k=2}^{\infty} s(k-2) \cdot z^k = \sum_{k=2}^{\infty}1 \cdot z^k$$

I started like this

it looks so confusing

then I wrote those terms in terms of Generating function G(s; z)

[vital dew]

arora:

[languid flint]

god, this question is awful

I would appreciate rays of help

[last timber]

:rays of help:

ok so

$S(k) = 2S(k-1)-S(k-2)+1$ is ur recurrence

[vital dew]

Commander Vimes:

[last timber]

I will write S(k) as $a_n$

[vital dew]

Commander Vimes:

[last timber]

$a_{n} = 2a_{n-1}-a_{n-2}+1$

[vital dew]

Commander Vimes:

[last timber]

$a_{n}x^n = 2a_{n-1}x^n-a_{n-2}x^n+x^n$

[vital dew]

Commander Vimes:

[last timber]

so, letting G(x) be generating function $\
G(x) = \sum_{k=0}^{\infty} a_kx^k$

[vital dew]

Commander Vimes:

[languid flint]

[last timber]

are initial cond given?

[languid flint]

yes s(0) = 2 and s(1) = 11/2

[last timber]

ok so by recurrence $\
G(x) - 2xG(x) + x^2G(x) = 1$

[vital dew]

Commander Vimes:

[languid flint]

umm how did you get 1?

[last timber]

ok so look

if i've some series
$a_0+a_1x+...+a_nx^n+...$ where $a_i$ is i-th term of recurrence

[vital dew]

Commander Vimes:

[last timber]

if i would multiply it by x for example

i will get all coefficient shifted

do u see that?

[languid flint]

yes

[last timber]

so recurrence says that for example a[3]-2a[2] = 1

for example

then in order to match coefficients i multiply recurrence

$\sum_{k=0}^{\infty} a_kx^k - 3x\sum_{k=0}^{\infty} a_kx^k + \sum_{k=0}^{\infty} a_kx^k + x^{2}\sum_{k=0}^{\infty} a_kx^k = 1$

[vital dew]

Commander Vimes:

[last timber]

oh i did something wrong haha

lemme coorect it

ok so $G(x) = \sum_{k=0}^{\infty} a_kx^k$

[vital dew]

Commander Vimes:

[last timber]

and

$G(x) = \sum_{k=0}^{\infty} a_kx^k = \sum_{k=0}^{\infty} 2a_{n-1}x^n-a_{n-2}x^n+x^n$

[vital dew]

Commander Vimes:

[last timber]

$G(x) = \sum_{k=0}^{\infty} 2a_{n-1}x^n-a_{n-2}x^n+x^n
= \sum_{k=0}^{\infty} 2a_{n-1}x^n-\sum_{k=0}^{\infty}a_{n-2}x^n+\sum_{k=0}^{\infty}x^n$

[vital dew]

Commander Vimes:

[last timber]

$2\sum_{k=0}^{\infty} a_{n-1}x^n-\sum_{k=0}^{\infty}a_{n-2}x^n+\sum_{k=0}^{\infty}x^n$

[vital dew]

Commander Vimes:

[last timber]

btw last summation is just 1/(1-x)

oh i now noticed

in the beginning i suppose i should've usen initial conditionsx

$G(x)-2-11/2 = 2\sum_{k=2}^{\infty} a_{n-1}x^n-\sum_{k=2}^{\infty}a_{n-2}x^n+\sum_{k=2}^{\infty}x^n$

[vital dew]

Commander Vimes:

[last timber]

that seems for me to be correct

grmm

@languid flint are u here?

ah i got wrong reccurrence

[languid flint]

yes

$2\sum_{k=0}^{\infty} a_{n-1}x^n-\sum_{k=0}^{\infty}a_{n-2}x^n+\sum_{k=0}^{\infty}x^n$
@last timber this one seems correct

[vital dew]

arora:

[languid flint]

I went out to clear my head, lol this thing gave me a headache

[last timber]

well i am now working on it

k should be 2

like i will now solve if it is meaningful will show

[languid flint]

I started out like this but I can feel it's a bit wrong 😅

ignore my clumsy handwriting haha

[last timber]

,w (1-2x+x^2)

[vital dew]

Display results online and refine query

Requested by Commander Vimes#7532

[last timber]

@languid flint both mine and urs are wrong

(

is it urgent for u?

like i will look at this later

[languid flint]

I was hoping to finish it by today 😅

[last timber]

,time @languid flint

[vital dew]

This user hasn't set their timezone! Ask them to set it using ,ti --set.

[last timber]

anyway, i just will now solve using charactersitic polynom and see what can be done

[languid flint]

it's okay if you wanna take some rest, I have about 12+ hours lol

I will try reading something on generating functions, god they look awful

[last timber]

wtf i am doing wrong ok so i have to rest

but