discrete-math

[amber hill]

$f(n)=3^n$

[vital dew]

usernamephobic

[brave yarrow]

Thanks

[grave moon]

can someone please solve it for me, please

[quaint star]

Solve it for you? No

Help you solve it? Sure

[amber hill]

I think s/he is giving an exam.

[grave moon]

i sent the solution i think is correct but you said its wrong

[amber hill]

Hint: It might be a reflexive relation.

[quaint star]

I know, so try to fix it

[grave moon]

they said it is not

[quaint star]

And pinpoint where you are stuck

Who said it's not reflexive?

I said the way you wrote it is wrong, not that it isn't reflexive

[grave moon]

i just need to make (a,a) is in S ?

is that where the problem is ?

3a_+ 5a is divisble

by 8 ofc

[quaint star]

Yes

You just wrote it in the wrong order

[grave moon]

other than that, its fine ?

[grave moon]

and, no im not in a exam

[eternal roost]

Solve the recurrence relation an = -3an-1 - 2an-2 + 2n for n ≥ 2 with initial conditions a0 = 3 and a1 = 0, needed some help with this. Wondering how i would do this

[amber hill]

characteristic equation, and then writing respective solutions with intial values

[eternal roost]

This is what i did so far

like what would be my next step

cause i dont see any sequence

[quaint star]

Yes. If you say 5a+3a=8a is divisble by 8, so (a, a) is in S for all a therefore S is reflexive. That's fine. Before you said (a, a) is in S therefore 5a+3a is divisble by a.

You still need to show the symmetric and transitive though

[amber hill]

Well, you have to find characteristic equation. Please refer to your notes once again.

[amber hill]

From speculation, it seems like that the pair elements are same in the relation.

[rustic steppe]

So I proved this with lattice paths but I want to try to interpret it via subsets:

any ideas how?

I really am not so sure.

The proof via lattice paths essentially interprets the right side as the paths from the last east step taken

[reef thistle]

To make a subset of k elements from n elements, consider what possibilities there are for the largest element. For each case, figure out what possibilities are there for the other k-1 elements.

[rustic steppe]

oh neat! thanks!

[distant bobcat]

If I want to show that a bipartite graph G with a complete matching has a deficiency $\delta(G) = 0$, does this just follow directly from Halls theorem? Since the deficiency is given as $\delta( G) = max_{A \subseteq x}{ \lvert A \rvert - \lvert P(A) \rvert $, we know that $ \lvert A \rvert \leq \lvert P(A) \rvert$, so if $ \lvert A \rvert = \lvert P(A) \rvert$ then naturally $\delta(G) = 0$, but what happens for the second case $\lvert A \rvert < \lvert P(A) \rvert$?

[vital dew]

Fredrikpiano

[distant bobcat]

Does this last part lead to a contradiction perhaps since it says that you would have a negative number of vertices unmatched? So then $\delta(G) = 0 $ for the later part as well?

[mystic moss]

@distant bobcat not exactly sure what you’re saying, but if you can show that the deficiency needs to be both at least 0 and at most 0 then you’re done

[distant bobcat]

yes, thats what I showed thanks!

[sour brook]

Just had a question about what this meant: A⊆B⇔Ā∪B=U Should I read this as A⊆B -> Ā∪B=U and Ā∪B=U -> A⊆B? Am a bit confused about the =U bit

[unreal stump]

Yes

Read P iff Q as P implies Q and Q implies P

[sour brook]

great thanks. would it be right to say that as Ā∪B=U and Ā∪A=U (complement law), A = B?

[unreal stump]

No

Because B can contain elements of A along with some elements of A'

You can conclude A belongs to B

[sour brook]

hmmm any clue on getting started with proving this would be appreciated

[sour brook]

this from the complement law? or from the LHS of the original A⊆B⇔Ā∪B=U?

[unreal stump]

Let's say B doesn't contain some element of A,call it x. Now x is in the universal set,which implies x is in A' or x is in B

But x is not in A'(since x is in A) and x is not in B(by hypothesis),leading to a contradiction

So,B has to contain every element of A

[sour brook]

(processing...)

[haughty garden]

Take U = {1, 2, 3, 4} with A = {1, 2} and B = {1, 2, 3, 4}. Clearly A’ U B = {1, 2, 3, 4} = U. And A’ = U \ A = {3, 4} so A U A’ = U. But A and B aren’t the same set

[sour brook]

Let's say B doesn't contain some element of A,call it x. this part is setting up the not p in the start of the proof, right?

[unreal stump]

Yes

(P is "A is a subset of B")

[sour brook]

thanks, will continue working along this train of thought 👍

[weary tiger]

Is there a term for a directed graph where each vertex points to at most one vertex? (It doesn’t matter how many vertices point to it.)

[trail steppe]

@weary tiger https://en.wikipedia.org/wiki/Pseudoforest

[unreal stump]

Pretty convinced graph theory is just geography

Or wherever you study about forests

[weary tiger]

Why is that definition equivalent to what I described?

[minor dagger]

nah its where you study sadness

[trail steppe]

@weary tiger ?

[weary tiger]

Thanks

[trail steppe]

Unfortunately other than Tarjan from a Google scholar search I don't see many prominent people who work on it

And Tarjan's work was 1988 which is a bit dated

[limpid fern]

people help with math so darn quick

[amber hill]

nope, dark letters on dark mode doesn't make sense at all

[gloomy panther]

no

[sour brook]

are parts of it wrong? or the whole thing?

[amber hill]

@sour brook he is trolling

Yes, it makes sense. @sour brook I believe it is correct.

[weary tiger]

Let $G$ be the directed graph with vertex set $\mathbb{Z}$ and an edge going from $x$ to $x+1$ for each $x$ in $\mathbb{Z}$. What kind of graph is $G$? A directed rooted tree, a polytree, or what?

[vital dew]

lugita15

[weary tiger]

Sorry what?

[weary tiger]

New question: is there a term for a polytree in which every vertex has outdegree 1?

[haughty garden]

https://math.stackexchange.com/questions/737161/is-there-a-name-for-a-directed-graph-in-which-every-vertex-has-outdegree-one

[weary tiger]

@haughty garden OK, let me ask this: Is there a complete classification of polytrees whose vertices all have outdegree 1? Can you decompose them into in-trees plus connections between in-trees?

I’m interested in the case when you have countably infinite vertices.

Are these the only shapes you can have?

Where each B_n is an in-tree

[sour brook]

Is this a valid use of the simplification rule of inference? p ^ q —> r becomes p —> r cos p ^ q becomes p

[turbid cargo]

I don't believe so @sour brook

In order to introduce an implication you need to assume something

[sour brook]

Thanks I found something online to the extent too. What you said confirms that

[turbid cargo]

Yeah, and by assuming p you would want to end up with r, so you can introduce the implication

[last timber]

p = T, q = F, r = F. then p ^ q -> r is true but p -> r is false

[errant bear]

just post it

[last timber]

ok, so e.g look at p -> t and not t
can you see that not p follows?

then you have not p and r -> not s (e)
and not p or q -> r (a)
since not p is true, we should have r true thus
not s true and finally not q

[sour brook]

Ok, but these don’t seem to use the rules of inference

[last timber]

i mean i do not write them formally

but it uses

not p OR q -> r
not p
therefore not p OR q, therefore r

e.g

[sour brook]

Hmmm thanks so much

I’ll look them up closely

[sour brook]

Erm... which rule of inference is this? Cos not p only speaks to part of not p OR q which itself is part of an a —> b conditional statement

[last timber]

@sour brook yes look

not p
thus not p OR q

and not p OR q
not p OR q -> r

thus r

[sour brook]

This Addition law is always a bit iffy!

q comes out of nowhere

[last timber]

i mean

if A is true

A or B is true always

[frozen tapir]

Is there a quick way to find this formula? I know it's a 4th grade polynomial and I get a system with 5 unknowns, but is there a faster way?

[last timber]

induction

[frozen tapir]

You can prove it with induction, but I want to find the formula first

[last timber]

consider

[vital dew]

$\frac{f(b)-f(a)}{b-a}=f'(\xi)$

$\frac{f(b)-f(a)}{b-a}=f'(\xi)$

[last timber]

ans see what happens when each summand term is expanded

[frozen tapir]

Uhm I see what you mean, however, do I logicalli get to that?

[last timber]

wym

[frozen tapir]

Like, what process leads me to think that (k+1)^4-k^4 is the first step of finding the formula?

I mean, where does (k+1)^4-k^4 come from?

[last timber]

i've taken it out of my ass

but in general the point is that

(k+1)^n-k^n is polynom of degree n-1

because of this pormula

[frozen tapir]

Ok, that makes sense, however, how can I know it's gonna be useful for my problem? I know it is of course, I know how to find the formula from there, it's just that this first step sounds like something I have to memorize without too much logic behind it

[last timber]

@frozen tapir i mean look a = k+1, b = k thus a-b reduces to 1

and you have polynomials with nth power thus summing you get sum needed participating in the sum

[last timber]

and like there is no "how you can know this is useful"

it is like heuristics

[weary tiger]

nice

[weary tiger]

im good with i but i really dont know how to go about ii

[ocean coyote]

I think this is calculus actually

[bronze cosmos]

^

[ocean coyote]

try in #calculus

[arctic cloud]

quick question

{a,b}={b,a} always, right?

[quaint star]

Yes

[grave moon]

We can count
C union D'
But counts the elements in D ?

[errant bear]

what

[grave moon]

Lol

Venn diagram

[errant bear]

"We can count
C union D'
But counts the elements in D ?"

[ocean coyote]

"It also proposes a more practical scheme that uses a special module called recryption box to assist homomorphic function evaluation"

can someone help me grok this

what are the prerequisites to understanding this

I'm pretty sure I understand what a homomorphism is

but not homomorphic function

is that homomorphism of two functions?

groups of functions?

[austere urchin]

hiiiiiiiiiiiiiiii

@everyone whos good at discrete here?

ples come to private and dm me

pls i actually need help

[drifting sail]

these channels are exactly for that, now if you want us to do your work for you that's not permitted as per the rules of this server

[austere urchin]

nono i just need a little help with a few questions

like there a few things i cant understnad

if u can explain and solve itll be great

[austere urchin]

can u show me how to solve this?

[coral raven]

get a4 from a5, then get a3 from a4?

seems easy enough

[austere urchin]

easy

thanks

answer is 2. right ?

[coral raven]

think so?

[daring crater]

How to I obtain the solution in the final lines (I understand everything up until that point). I marked the section in red

Why cant I just take a_n = n (for which f(n) = n-1). Why do I have to consider a linear combination?

[coral raven]

so you have two linearly independent solutions to the second-order recurrence relation

but second-order recurrence relations are special in that if you have two such solutions, any linear combination of them will also work

the trick is that only one specific linear combination will satisfy any specific initial conditions given

[daring crater]

Ah ok I see

If all the initial conditions were met by f(n) = n-1 then I could use that, right? If we would change the initial conditions to a_0 = -1 and a_1 = 0

[coral raven]

if it works, it works

[daring crater]

Thank you for your help 🙂

[errant bear]

of course :)

[karmic nymph]

for the option where "if a word starts with xx and ends with x then A accepts it"

shouldnt that be a true statement?

If we assume that we have a word that starts with xx and ends with x, This automaton accepts it?

[crisp barn]

what would be a good way to estimate x-subscript-0 here

[errant bear]

clearly x_0 = sqrt(S)

[drifting sail]

that's Newton's method for the function f(x)=x^2-S. Any x_0 greater than 0 should converge to \sqrt{S}, while points less than 0 should converge to -\sqrt{S} -- these are exactly the basins of attraction for these two roots. Here's an example (source: http://www.acme.byu.edu/wp-content/uploads/2017/01/Vol1B-NewtonsMethod-2017.pdf):

[sterile otter]

Disecret math.

[ocean coyote]

Characters["Discrete maths is cool"] out={"D", "i", "s", "c", "r", "e", "t", "e", " ", "m", "a", "t", "h", "s", " ", "i", "s", " ", "c", "o", "o", "l"}

[novel spire]

Hey y'all! I need some ideas.

Trying to come up with more types of problems that can basically be reduced to rearranging the letters of a word where some letters are repeated.

[obtuse lance]

you could do something with scheduling different blocks of time throughout a day

[novel spire]

Oh nice, I like it

[obtuse lance]

same as (b) isn't it?

[reef thistle]

whoops that's already (b)

Number of ways to give n (indistinguishable) coins to k children, how about this.

[obtuse lance]

also, maybe a kind of strict thing on making necklaces with beads, although I feel like that's overdone lol

[spring ether]

what's a conventional alternative notation to XOR that isn't $\oplus$ (which I'm using for the direct sum) ?

[vital dew]

xdres

[obtuse lance]

what's the context where you're using both simultaneously, seems like a rare occasion

[coral raven]

looks ugly but it works

[spring ether]

looking at elementary abelian 2-groups, in which the group operations is basically bitwise xor

but the group structure is a direct sum of C_2

[obtuse lance]

if it's the group operation, I'd just use regular + maybe

[spring ether]

I'm using real numbers so + and . already have full time jobs

investigating associative metrics

[spring ether]

if I don't find something prettier I'll use it

where did you find that notation?

[coral raven]

wolfram

[spring ether]

cheers

[ocean coyote]

I just wanted to say that this is the best beginner book on graph theory that I have found https://www.amazon.com/Introduction-Classic-Classics-Advanced-Mathematics/dp/0131437372/

[nova star]

how many ways u can arrange distinguishable* objects in distinguishable containers

i have a book full of these if u want screenshots btw

also, how many hands of 5 cards can be drawn from a deck of 52 cards for 4 players

how many ways can group of children be arranged in groups of 4 if 3 groups have to be assigned and there are 50 children

what is the coefficient of x^3 * y^2 * z^5 in (x+y+z)^10

all of these use the same formula

(total number of elements)! / (elements in first group)! * (elements in second group)! * ...

sorry, small error, super sleepy, fixed it now tho

[oak notch]

Is data structures a part of Discrete Math?

[reef thistle]

a bit...

[weary tiger]

discrete math is used to analyze data structures

[low gale]

Hey guys can you please explain to me what should i do with this exercise? is it like a modus tollens (truth generator) or is it something else that i can't understand from this exercise?

Let p, q, r, s and t be statements variables. Use the valid argument forms to deduce the conclusion, ¬q, from the premises, giving a reason for each step. (a) ¬p ∨ q → r (b) s ∨ ¬q (c) ¬t (d) p → t (e) ¬p ∧ r → ¬s

[reef thistle]

hmm, looks like a, b, c, d, e are the premises @low gale

basically you are suppose to deduce not(q)

[low gale]

So the propositional formula p ∧ q → ¬r could be written as p /\ q -> ~r, as p and q => not r, or as p && q -> !r ? @reef thistle (for the first one) or not?

[reef thistle]

hmm... p and q implies not(r), yeah...

but (c) is the simplest so I think it's a good idea to start from there

[low gale]

i want it for a mid term exam and i am kinda stuck in which way i should write it correctly to achieve full points ...maybe i overthink it

[reef thistle]

you should use those symbols that you used before

like
¬t (c given)
¬t → ¬p (contrapositive of d)
...

[low gale]

hmmm ok i will search it a little bit more

thank you

[bronze rain]

https://cdn.discordapp.com/attachments/488104216678760469/793449596381691924/309013702982500352.png

I wonder if there is a nice combinatorial way for showing b_1 is 0. Something like for Euler's pentagonal number theorem on Wiki.

[bronze rain]

For any m, a good partition of m is defined as follows: a partition of m into 4 parts: m1, m2, m3 and m4 such that m1 is partitioned into a distinct positive parts, m2 is partitioned into b distinct non-negative parts (so we allow 0 to be a part now), m3 into c distinct odd parts and m4 into d distinct odd parts and a - b + 2c -2d =1. The size of a good partition is a +b + c + d. One way of proving the required result is to find an involution that flips the parity of the size of the good partition.

[floral field]

I got this problem from Andrews’ Number Theory book, and was wondering if someone could check it. And how would it generalize for weights up to n pounds?

[reef thistle]

looks reasonable

[amber hill]

@floral field I remember doing a similar problem, I mean getting every other weight for 40 pounds. So, we can get any number 1-40 if we take linear combination of 1,3,9,27.

Is what what you were looking for?

I mean something similar.

So, yes I think 111111_{2} is the correct answer.

[remote mulch]

if there is no bijection relationship between two sets

does that necessarily mean one set is bigger than the other

since they both can be the same size but some of the elements in the codomain is not mapped onto

[pale epoch]

two sets have the same cardinality iff there is a bijection between them by definition

so if there is no bijection between two sets, they do not have the same cardinality

and hence one must be "bigger"

actually its not that easy, since its non trivial that "not having same cardinality" implies that "one set is bigger"

[bronze rain]

How do you define bigger here: B is bigger than A if there is a one-one map from A to B such that there is an element of B which is not an image of any a in A?

[unreal stump]

No

B has a different size than A if there is no bijection between A and B

[pale epoch]

generally there are two ways

[unreal stump]

There is a 1-1 map between 2Z and Z satisfying your condition

[pale epoch]

you say |A| <= |B| if there is an injection from A to B

and then you say |A| < |B| if |A| <= |B| and not |A| = |B|

[bronze rain]

I meant after knowing that there does not exist a bijection

[pale epoch]

(the alternative is via surjections)

[radiant trail]

Let $M = {1, 2, 3}$ and $f = id_M$ would $f(M) = {1, 2, 3} or f(M) = {{1}, {2}, {3}}$ ?

[vital dew]

MeesyIce

[pale epoch]

the former

[radiant trail]

thanks 😄

[drowsy tiger]

Is the ans 2?

[turbid cargo]

Inclusion-exclusion principle, and yes the answer is 2

[drowsy tiger]

Got it! thank you 😄

[safe oxide]

Could someone explain the difference between {1,2} x (1,2) and {1,2} x [1,2]?

Working on the Cartesian product portion of Book of Proof

It's not made clear what the difference in discrete mathematics is between (1,2) and [1,2] or how that might affect the product of the sets. Any help appreciated 🙂

[last timber]

(1,2) can be read as pair or open interval

i assume that it is interval

so (1,2) does not include points 1 and 2

thus {1.2} x (1,2) won't include pairs 1x1, 1x2, 2x1 and 2x2

while [1,2] includes points 1 and 2

thus {1.2} x [1,2] includes pairs 1x1, 1x2, 2x1 and 2x2

@safe oxide

[safe oxide]

Ah, that makes sense. Thanks for the clarification!

[remote mulch]

"A function f from a set A to a set B is an assignment of exactly one element of B to each element of A."

I just cant get my head around the wording of this definition for a function

Could someone explain this to me pls🥲

Like an element of B doesnt necessarily have to be assigned to every element of A does it?

[drifting sail]

yeah, not necessarily.

the point is that for each $a\in A$ there's a unique $f(a)\in B$.

[vital dew]

derivada.schwarziana

[drifting sail]

so a point in A can't have two different images.

[remote mulch]

Ok thx

[quaint star]

An analogy. Think of a class of 20 students writing a test. There is a function from the set of students to the set of all possible marks. Every student must have a mark, but not every mark has to have a student that got that mark. And multiple students can get the same mark.

So each element of A (each student) has assigned to it exactly one element of B (one mark)

[remote mulch]

Yh its become a bit clearer now thanks

[rough parcel]

https://cdn.discordapp.com/attachments/490557019623915520/794323136241074176/image0.jpg
Could someone tell me if this 2 tables are logically equivalent to each other ?

[errant bear]

which 2

[limpid fern]

so 1 means true and 0 means false

@rough parcel I can't see the other table

I can barely see it

the greenish one

[earnest kite]

https://youtu.be/qQMsLAIqtmU

[proven shard]

this is amazing

[remote mulch]

The condition for an injective function is ∀a, b ∈ A (c1::f(a) = f(b) → a = b)

Why is the first part ∀a, b ∈ A and not ∀a ∈ A, b ∈ B?

[bronze cosmos]

i’m assuming f:A->B. the inputs a and b come from the domain A, otherwise f(b) makes no sense

probably confusing they use a and b. perhaps using x and y instead would be easier

[remote mulch]

oh right

so two different inputs

if their output is the same then they are the same value

[bronze cosmos]

any two inputs*

[remote mulch]

^^

[drowsy tiger]

in the De Morgans law, are the entities (which I have circled) the same thing?

[obtuse lance]

no, order of operation is different

top one is negating them first then *

second one is negating after

[drowsy tiger]

got it! thank you

[glacial flame]

What is SOP expression? Or POS?

[drowsy tiger]

SOP = sum of product

[haughty garden]

Complement of the “Sum of Product” is the “Product of Sum”

[drowsy tiger]

yeah, but wouldn't the expression be "product of sum" for f', and not f?

I want to find the "product of sum" for f

[glacial flame]

I dont know what if you complement that

And apply DeMorgan

[drowsy tiger]

you mean again?

[haughty garden]

You would find f’ by applying De Morgan

And then take the complement again to find f’’

And observe that f = f’’

[drowsy tiger]

ohh got it.

[glacial flame]

You should ask these questions in proofs and logic channel

[drowsy tiger]

well, I am completely new to discrete mathematics (and, also new to this server) ,so I don't know which questions to ask where...

[glacial flame]

This is math logic question, not discrete math 🙂

[drowsy tiger]

hmm okay, I asked it here becuz it is taught in my discrete mathematics course.

[glacial flame]

np

[loud copper]

how does this proof make any sense

they never showed a winning strategy even exists in the first place

they're assuming what they're trying to prove

[errant bear]

are you confused about how they know theres two cases, or that the move would be a "winning strategy" for the player

[loud copper]

both i think

[errant bear]

ok lets look at a 2 by 2 cookie grid

i might not be the best at explaining this but i think itl help

[last timber]

thy nas

thiy mean

that

[loud copper]

wat

[errant bear]

so say i go first, what happens if i eat the bottom right cookie

[last timber]

m x n case

is the sae

as

[loud copper]

???

[last timber]

(m-1) x (n-1)

[loud copper]

vimes stop it

[loud copper]

u always win no matter what i do

[errant bear]

ok right, so in say, a 5x5 grid, what happens if i eat the second from the top, on the left most column

you can force a win by picking the second cookie from the left on the top row

[loud copper]

mhm makes sense

[errant bear]

so all other moves prior to those moves can be forced

thats kind of the intuition behind it?

[loud copper]

wait how ?

[errant bear]

mmm, ok lets look at 3x3, generalizing it seems to be too much work lol with even and odd cases

so if it ends up in the scenario, where its just the a(1,1), a(1,2), and a(2,1) cookies left, (the top left), (second from left on top row), (second from top on left column), and its my turn, then im guaranteed the win

this was from the 2x2 example

[loud copper]

true but thats if it ends up in that scenario

what about the other cases

[errant bear]

true

so i want to force that scenario

mm

this seems like a lot of cases lol, hold on

[loud copper]

ye i was trying it on paint

i couldnt force this scenario

[errant bear]

ok so
ooo
ooo
ooo is our start

say i go first with bottom right

you then want to make a move where it leads to your turn, picking from either a 2x2 grid, or something like
x x x
x
or
x x
x
x

mm, this might be the wrong approach

to explaining this

do you see how, in an m x n grid, if the first player goes in the bottom right, the second players move "absorbs" the first players move?

[loud copper]

yeah kinda

any move the second player makes absorbs the bottom right piece

[errant bear]

yes

eh i feel like im about to just restate what your book says lol

ok but, there must be a winner regardless of the m and n

right?

[loud copper]

yeah i feel that temptation too now with that whole absorption thing

yeah ties arent possible

winner exists but i dunno if a strat exists for any player

[errant bear]

mmm idk how to word this correctly, but since a winner is guaranteed, and you can force scenarios, one of the players must be able to force a win at some point, and since you can "nullify/absorb" the immediate prior move, you arrive at the cases

ik it doesnt sound like, rigorous, idk how to describe it better

[loud copper]

yeah i get it

its about feeling it in ur heart

this was a really weird one ngl

anyways thnx for ur time

rly appreciate it

[errant bear]

idk maybe someone else can describe it where it doesnt feel heuristic

[obtuse lance]

maybe the real math was the friends we learned along the way

[errant bear]

kiss me

[loud copper]

😳

ok close ur eyes

[obtuse lance]

spits poisoned cookie into your mouth

the real winning strategy

[loud copper]

what if ur opponent doesnt offer to kiss u

then ur in a real pickle

[drifting sail]

what did I just walk into lmao

[last timber]

then rape them

[loud copper]

[bronze cosmos]

what the fuck is going on in this channel

[dire void]

I'm trying to understand the definition of an ordered pair using sets

so a couple of examples that make sense in my head

1. {x,x,x,x} = {x}
2. { x , y } = { y , x }
   3.{ {x},{x} } = { {x} }

my question:

{ {x} , {x,y} } = { {x,y} , {x} } =?= { {y,x} , {x} }

[dire void]

really?!

[last timber]

@dire void yes because all sets have element {x}

and {x,y} = {y,x}

ordered pair (x,y) = {x,{x,y}}

[dire void]

what?!

[last timber]

you can see that in that case (x,y) != (y,x)

[dire void]

hold on. lemme refer to my notes....

[vital dew]

$\frac{f(b)-f(a)}{b-a}=f'(\xi)$

[last timber]

oh, you use that

well it is close to mine

[dire void]

ffs, there are at least 2 equivalent definitions of order pair?!

[last timber]

yes

there are many ways to define pair

[dire void]

yeah, even wiki says there's a lot of ways to define this

[last timber]

the point anyway is to make us able to distinguish (x,y) from (y,x) and (x,x) from (x)

[dire void]

yes. i agree that it's important to be able to distinguish (x,y) as distinct from (y,x)

[unreal stump]

Base case is P(5) being true

P(5^k)=>P(5^(k+1)) is the induction step

[paper wing]

Does anyone know how I could prove this? I made some Venn diagrams and i dont think its the same but I think its not supposed to be solved like that

[quaint star]

@paper wing What does it mean for A to be a subset of B?

[paper wing]

I think it means that if B is {1, 2} then A is { ∅ , {1}, {2}, {1, 2}} @quaint star

[quaint star]

No

That's power set

[paper wing]

So the opposite?

[quaint star]

What's the opposite?

[paper wing]

if B is {1,2} then A is ∅ or {1} or {2} or {1,2}

so not all of them together

[quaint star]

Well, yes

Those are the subsets of B

But what's a definition?

You need to have a definition so that you can show it is satisfied

[paper wing]

the definition of subset?

[quaint star]

Yes

A is a subset of B if...

[paper wing]

it means that the elements of A are members of set B

[quaint star]

Yes

So if x is an element of A, then x is an element of B

[paper wing]

so {x} would be a subset of {x,y}

yeah

[quaint star]

That's an example, yes

So $A \subseteq B$ if $ x \in A \implies x \in B $

[vital dew]

Lunasong

[paper wing]

But what about (A∩C)⊆B .

After the arrow

[quaint star]

Well, apply the same definition

That is true if every element of A intersection C is an element of B

[paper wing]

So thats always true right

[quaint star]

So, you assume A is a subset of B. Then you want to show A intersection C is a subset of B. So you let x be an element of A intersection C, then you have to show x is also an element of B.

[paper wing]

if the firs tpart is true

[errant bear]

yes

[paper wing]

So is it proven like this?

A(x) B(x,y) C(x, z)
A is a subset of B here, and A∩C is {x} here. A∩C is still a subset of C so the implication is true

@quaint star

[quaint star]

No

You can't just make up sets

You have to prove it in general

[paper wing]

Can you show me how to prove it in general? if it doesnt take too long since i dont really know how to do that

[errant bear]

what do you know about A intersect C

[quaint star]

I will show you how to prove something else

If $A \subseteq B$ then $A \subseteq B \cup C$

[vital dew]

Lunasong

[last timber]

[paper wing]

@errant bear We dont really get any info about A

Is it (A⊆B)UC

for you equation luna

[quaint star]

Bruh, what would that mean?

It's $A \subseteq (B \cup C) $

[paper wing]

idk lol

I just wondered because there were no parentheses

[quaint star]

Let $ x \in A$. Since $A \subseteq B$, that means $x \in B$. And that means $x \in B \cup C$. So an arbitrary element x of A is also an element of $B \cup C$, so A is a subset of i5

[vital dew]

Lunasong

[paper wing]

Alright I get that

Ill try to apply that to the other question

[quaint star]

So you assume the part that is given, and use that to prove the second part

[paper wing]

hmm for my example I got this

Let x ∈ A. Since A ⊆ B, that means x ∈ B

That does not necessarily mean x ∈ (A∩C) since it is possible that the intersection of A and B have nothing in common.

This means that x ∈ ((A∩C) ⊆ B) is not always true.
So the claim as a whole is not true.

Is that wrong? @quaint star

[quaint star]

Yes

The claim is true

You want to show A intersection C is a subset of B

So you should start by letting x be an element of A intersection C

And then show that x is an element of B

[paper wing]

So if A and C have nothing in common the empty set is still a subset of B right? Should I prove it like that?

[errant bear]

what do you know about the elements of A intersect C

[paper wing]

∅ is always a subset of both A and C so the intersect is always ∅ ?

Let x ∈ A. Since A ⊆ B, that means x ∈ B

That does not necessarily mean x ∈ (A∩C) since it is possible that the intersection of A and B have nothing in common.
An empty set would be the result.

This means that x ∈ ((A∩C) ⊆ B) is always true because ∅ is always a subset of B
So the claim is true.

Thats what i have now

[quaint star]

No. Do what I said

Start with 'Let $x \in A \cap C$'. Then show that $x \in B$

[vital dew]

Lunasong

[paper wing]

Let x ∈ A∩C. This means x ∈ A. A ⊆ B so x ∈ B

Is this a step in the right direction or not? @quaint star

[quaint star]

That's it

[paper wing]

Thanks man i think i get it now 🙂

[iron sleet]

Can someone help me with this one. I am to find the nth term in the sequence. So far I noticed the n^2 - 1 but i am a bit confused

<@&286206848099549185>

[weary tiger]

It looks like it's growing much faster than quadratic, looks closer to factorial

5760=5040+720
840=720+120
144=120+24
30=24+6
8=6+2
3=2+1

so an=n!+(n-1)!

can i post a question on discrete mathematics here, too?

or it should be in the question sections

No. God forbid u post a discrete maths question in the discrete maths channel

[drifting sail]

lmao

both are fine really

[weary tiger]

oookay

basically i need help because i don't know how to approach this

it should be proved by combinatorial proofs

n and m are positive natural numbers

reminds me of stirling numbers

and n^k represents this expression

yeeah, the {m k} thing is stirling number

and p^q thing is basically this

i have solved equations where it's easier to connect them to an irl example

but here i'm not even sure how to start

and i'm not sure if i have to prove that this {m k} is a stirling number

because the task clearly says that {m k} represents the number of ways to partition a set of m objects into k non-empty subsets which is the definition of a stirling number

[ivory sinew]

n^k is the number of ways to select k objects from a set of n objects in order

n^m is the number of ways to select one of n objects, m times in order

Try to establish a relationship between them using these interpretations

Think of equivalence classes

[livid drum]

@weary tiger
Long and very telling hint:

And completing spoiler (no need to expand unless genuinely stuck):

[ivory sinew]

Eh there's a simpler method

||
Consider (a1, a2, ... am), where each element corresponds (possibly neither injectively nor surjectively) to one of n objects. There are n^m ways to achieve this. Construct the k equivalence classes, of which there are {m k} possible arrangements. And assign a unique object in n to each equivalence class, which there are n^k ways of doing.
||

[ocean coyote]

A father threatens his son: 'if you are not quiet you will get a slap!', and he
proceeds to administer the slap even though the child had immediately become
quiet. from the point of view of mathematical logic, this man is not at fault: the
truth table for $\Rightarrow$ shows that, by becoming quiet, the child makes the implication
true regardless of the truth value of 'you will get a slap' ... (a good father should
have said 'you will get a slap if and only if you are not quiet').

[vital dew]

0000000000

[ocean coyote]

from a book

after a slight correction of formalism the boy probably asked him to define quiet and define slap

😆

[limpid fern]

if you are quiet you will not get a slap

both logically equivalent

if you are not not quiet, you are quiet

[livid drum]

@ivory sinew @weary tiger I see what you mean. Yes that is beautiful. It is analogous to the distinction between Reiman's way of counting (in the order in which they appear) vs Lebesque's way (in bulk over equal denominations)
||The number of functions from m→n is argued by two separate ways. (1) Reimann counts his functions by considering in order, the first input 0∈m having n possible values, the second input 1∈m having again n possible values, ... and so on, eventually affirming the n^m total possible specifications. (2) Lebesque on the other hand looks at the class of inputs which maps to a fixed output. He looks at the class of inputs which maps to 0∈n, the class which maps to 1∈n, etc. This forms a partition over the set of inputs. A function is identified by first specifying the number of distinct outputs witnessed, say k (from 1 to n), then by specifying a partition of m into k classes (there are {m, k} of these), and finally by specifying the output value of each of these classes (there are n!/(n-k)! ways of doing this). Lesbesque affirms there are sum_(k=1)^(k=m) {m, k} n!/(n-k)! many functions. ||

[limpid fern]

everything makes sense once it's a sentence

[errant bear]

[limpid fern]

@errant bear hey namington

$p \implies q$ = $\neg p \implies \neg q$

[vital dew]

00001011011110001111010110000

[limpid fern]

$\neg(\neg p) \implies p$

[vital dew]

00001011011110001111010110000

[ocean coyote]

$(p \implies q) = (\neg q \implies \neg p)$

[vital dew]

0000000000

[limpid fern]

if dog eats, then eats fast, not eats fast means not dog

ohh

if human, then burp, if not burp then not human

[distant bobcat]

I'm aware of the relation matrix comprising of zeros and ones, but if I have a relation that is a function how will the matrix then look?

I think if I let the rows correspond to the domain and the columns correspond to the codomain then each row will have at most one 1 and the rest of the entries are zero.

[last timber]

@distant bobcat yes, if you e.g define i-th row to consist of entries such that (i,j) entry is 1 iff a_i R a_j and R is function then you should have exactly 1 nonzero entry at each row

[distant bobcat]

Then does this not allow surjective functions? If we use the same definition for surjective functions dont u end up with more entries in the same row?

[last timber]

wym?

no

because codomain is then columns

and this defn surjective functions are these not having zero columns

[distant bobcat]

yes, you are right. I guess I was thinking about a scenario with only surjective functions and trying to define it in such a way that would allow multiple zeros for the rows.

[zinc marsh]

The fundamental theorem of finite abelian group says: "Every finite abelian group is isomorphic to a direct product of cyclic groups". How do I find these cyclic groups?

Consider Z/7Z, it is isomorphic to Z_6, how do I find it ?

(Z/7Z)^x I mean, the units in the ring

[zinc marsh]

Thanks slim. I mean how to find the decomposition

[zinc marsh]

@weary tiger Was in a dota match :D. But thanks !

[radiant trail]

how do i find the number of units in Integers mod n ? do i have to draw the addition multiplication table or is there another way ?

no

[weary tiger]

Okay, one more question, if I find the reccurence equation which is for example:
Fn = Fn-1 + Fn-2

through F1, F2, F3...

do i need to prove why Fn is exactly that?

[pale epoch]

what do you mean?

if you define F_n that way, it's by definition

[weary tiger]

yeah, but i've found the exact value of F1 and F2, after that I found F3

[pale epoch]

well, you need a "starting point" to employ a recursive definition

you need to know two consecutive values, otherwise that definition makes no sense

[weary tiger]

Yes

I found that F1 is 1 and F2 is 2

After that I found that F3 is 3, independently

And after that I saw that F3 = F2 + F1

is this enough to say that i have found the recurrence equation?

[pale epoch]

you "found" them?

[weary tiger]

Okay, let me start again but I will use the exact numbers, because this example values mess up with the fibonacci sequence, can i?

[pale epoch]

eh, sure

[weary tiger]

so my problem is:
How many words of length 𝑛 over the alphabet {𝑎,𝑏,c,d} such that the sub-word 𝑏𝑏, aa, ba, ab does not appear?

Let an be the number of words of length n who satisfy the condition above

If a1 is the number of words of length 1 which satisfy the condition above, a1 = 4 (a, b, c, d)

If a2 is the number of words of length 2 which satisfy the condition above, a2 = 8

I have found that a3 is 40 independently, without using the fact that i know a1 and a2

Can I say that because a3 = 4a2 + 2a1, Fn = 4 Fn-1 + 2Fn-2

[pale epoch]

no

it's a sign that you might be on the right way

but you have to find a way to build bigger words out of smaller words somehow

[weary tiger]

what do you mean by that? can you give me an example?

or i have to look for a4?

[pale epoch]

well, let's say i want a word of length n

let's look at all words of length n-1 that satisfy those conditions

so they don't have this as a subsequence

now no matter with what letter those words end, i can concatenate c or d

because none of ac, bc, cc, dc or ad, bd, cd, dd are disallowed

[weary tiger]

ookay

[pale epoch]

so i can build at least 4*a_{n-1} words of length n

when a_{n-1} is the number of words of length n-1

now, you can also build more, so you have to be somewhat smarter about that

but that's probably the idea

[weary tiger]

i see

so i should look for the cases where I don't have the disallowed subwords

thank you!

[quaint ermine]

Hey guys!

How can I get the z-transform of this function?

$f(t)=2^tcos(t+2T)u(t-T)$

[vital dew]

JoshMooner

[grim tapir]

conversion to DNF?

I have tried all simplification methods not sure what to do

[past iris]

I got
X'Y'+ZX'+XZ'+XY'

If I didn't make any Calculation error

(I used K-maps)

[loud copper]

what have u tried

[kind solstice]

I'm new to this i don't understand from where to start really

[loud copper]

have u learned that intersection distributes over union ?

[kind solstice]

they gave us a table that shows different things like that

[loud copper]

ye u just gotta apply these basic set theory properties

[kind solstice]

is it gonna be something like this for the first part?

[loud copper]

yeah u got it right

[kind solstice]

so

this becomes this?

[loud copper]

it does

[kind solstice]

and then like this for the whole exercise?

[loud copper]

mhm

[loud copper]

these ones should be intuitively obvious

[kind solstice]

judging by this it should remove that symbol?

[loud copper]

so you dont have to look at the table all the time

[kind solstice]

oh

[loud copper]

yeah you can

like all you're saying is take a set and add nothing to it, so you're gonna be left with the set you started with

[kind solstice]

so im left with this?

[kind solstice]

oh

[loud copper]

yeah simplify it further

same routine

[kind solstice]

i can't think of anything to simplify it further

[loud copper]

maybe now it looks familiar ?

[kind solstice]

?

[loud copper]

yeah thats one half of it

[kind solstice]

does it have to do with b u c?

[loud copper]

ok disregard what i said about distributing the A intersection B part

theres an easier way to simplify it

[kind solstice]

hm

how?

[loud copper]

im drawing

associativity

now apply the distributive law

inside the red brackets

[loud copper]

🥳

[kind solstice]

is there anything else i can do?

or is it done?

[loud copper]

whats B intersection B complement ?

what elements can have the property that it is in B and at the same time not in B ?

[kind solstice]

not sure?

[loud copper]

yeah exactly

no element can satisfy that property so the intersection is the empty set

[kind solstice]

ohhh

so it becomes

?

[loud copper]

yeh

you can lose the brackets

can u tell me why ?

[kind solstice]

umm

[loud copper]

[kind solstice]

idk xD

why?

[loud copper]

intersection is associative. so that means it doesnt matter which two u intersect first

the result is gonna be the same anyways

so theres no ambiguity when u write it without brackets

the same goes for union

[kind solstice]

ohhh because of this?

[loud copper]

nah thats different

[kind solstice]

oh

alright

[loud copper]

becuz of this

and this law is called associativity

[kind solstice]

oh

[loud copper]

yup

[kind solstice]

i did the a

but im stuck with b

[loud copper]

oh fuck im out

[kind solstice]

i don't understand that backwards thing

lmao

is this easier?

is there a calculator or something to do it? xD

[amber hill]

is this an exam problem?

[kind solstice]

no if i was doing an exam i wouldn't be able to chat on discord

[amber hill]

Since the problems are not related to each other

[last timber]

b) is quite easy but it is cumbersome computation

[amber hill]

hard to tell

[kind solstice]

it's an exercise so the professor can somehow boost our grade if we fail on finals

[amber hill]

so it's still not ethical?

[loud copper]

damn it alice i cant believe u used me like that

[last timber]

hi @loud copper

[loud copper]

sup vimes

[last timber]

inf soap

[kind solstice]

i didn't use you

[loud copper]

ive been bamboozled

bewildered

quite possibly fooled

[kind solstice]

tbh I understood better than the actual professor

[amber hill]

<@&268886789983436800> Is getting help on graded problems allowed?

[kind solstice]

it's an early university category, any exercise is graded regardless

[amber hill]

since you have learnt discrete maths the whole sem how are you new to discrete maths

[kind solstice]

i know how to do it

the answer is 8

i can take a picture if you want

alright

but we write the remainders differently so don't get confused

also don't judge my writing lol

we use + to show the remainder

last is 16 not 160 i just removed a wrong number

alright yeah

oh

that's a bit confusing xD

alright thanks

[jolly saffron]

@amber hill , do you need a solution for a set excercise now?

[grim tapir]

oh k - maps

i was hoping it wouldnt require that

people say you can do it with a distributive law but i cant seem to work out what form to get in to get that to be possible

$(x\lor{\neg{y}\lor{z}})\land{(\neg{x}\lor{\neg{z}})}$

[vital dew]

shriller44

[grim tapir]

like in this form i dunno if i gotta rearrange it some ho

Technically in this part of our course we shouldnt require the need for k-maps

[grim tapir]

can DNF involve literals by themselves in the chain of disjunction

[weary tiger]

Uncountable infinitife set - Uncountable infinitife set ? what the result ?

<@&286206848099549185>

[balmy socket]

@weary tiger it depends.

are you sure its "-"

also you gotta wait at least 15 minutes to ping helpers for future reference

R-Q is uncountably infinite and R-(R-Q) is countably infinite

but R-R is finite

and also R-[0,infinity) is uncountable infinite

the answer is "it depends"

[gritty crescent]

Theorem: A connected graph G has a closed Eulerian trail iff all vertices of G have an even degree.
The proof enclosed is from MSE, and resembles the one I came up with. However, the proof given in the book I'm consulting runs over a page in length, so I was wondering if this argument has a gaping hole. Could someone point the shortcomings in this proof(if any)?

[ivory sinew]

It's valid

But this is the converse of what you described

[gritty crescent]

So this only proves one direction of the proposition?

[ivory sinew]

Ye

In competition math it's taught that the edges of any connected graph with 2n vertices having odd degree can be drawn in n paths. And 1 path for no odd degrees.

[gritty crescent]

I don't follow.

[ivory sinew]

E.g. The edges of a connected graph with 5 vertices, 4 of which are odd, can be drawn in 2 continuous lines.

[gritty crescent]

Ah, okay, that makes sense.

[livid drum]

@grim tapir
Here might be the step-by-step conversion you're looking for:

[grim tapir]

jeez thats long

but thanks though

i didnt think you could distribute first part like that

[icy jungle]

can any anyone please help me solve this

[fathom warren]

Suppose a box contains 18 balls numbered 1-6, three balls with each number. When 4 balls are drawn without replacement, how many outcomes are possible. If order is matter.

I solved for this question ıf order is does not matter and use this method :
a_1+a_2+a_3+a_4+a_5+a_6 = 5 so C(6+5-1 , 5 )

but ı cant solved if order is matter

<@&286206848099549185>

[icy jungle]

can anyone help with the second one

<@&286206848099549185>

[weary tiger]

What does one-to-one mean and what does onto mean

[weary tiger]

How did you do the problem when the order does not matter

[hallow bluff]

One-to-one is injective and onto is surjective. Both would mean it is bijective

[rain stone]

I think that lime_soup was asking zatza rhetorically to get them started

[ocean coyote]

that depends if you think 1,1,1,2 == 1,1,1,2

these are different outcomes by some rules but they are the same if we only look at the symbols

you know that 1,1,1,1 will never happen

so you have {{1,1,1,1},{2,2,2,2}...{6,6,6,6}} in the set of impossible outcomes

you can do 6!-2!-6

wait no

6^4-6

,w 6^4-6

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by 0000000000#7632

[ocean coyote]

1 to 1 means for ever x in A in the domain of f there is a y in B in the range of f such that f inverse of y in B = x in A

the sin function is not one to one because there is ambiguity as to what exactly you want to get out when you perform the inverse of f

so the y->x is not unique

the point y maps to more than a single point x

so sin(x) is an onto function

I have never seen this with two inputs to the function so IDK what the answer is

[weary tiger]

[weary tiger]

cf.

[weary tiger]

This is not even technically correct and certainly gives people the wrong idea

it completely depends on what you define the target to be, from R to R since is neither invective nor surjective, from R to [-1,1] it’s surjective but not invective, from [0,pi/2] to R it’s invective but not surjective, from [0,pi/2] ito [0,1] it’s bijective

And yes you can claim this is obvious if we both know what we are talking about

But if you thought you were explaining this to someone who doesn’t know, don’t pretend it’s obvious

[errant bear]

sin(x) is my favorite onto function

[ocean coyote]

I thought that I was explaining it to someone who didn't know so I gave them the short version that they could actually understand

[fathom warren]

ı use permutation and ı solve this quesition case by case

[weary tiger]

Ah that makes sense

You tell someone who doesn’t know that ‘y maps to more than a single point so sin(x) is onto’

So then someone who doesn’t know thinks surjective means non-injective

You are right it is much better to give people this idea so they can actually understand

My apologies

[distant bobcat]

I read somewhere that if you have a payoff matrix for a pure strategy (i.e rock-paper-scissor) then its possible to show that there is no Nash-equilibrium by checking if there exists no elements that are both the minimal in a row and a maximal in a column. Has anyone heard of this? Im not sure why this works intuitively...

[stable temple]

what does this mean?

[unreal stump]

[ ] is a function which returns 1 if p is true

And 0 otherwise

Think of bools in a programming language

[stable temple]

🤔

i saw it here, but i dont really understand how they got that from the initial expression after F(z)

[unreal stump]

f_n=f_(n-1)+f_(n-2)?

That relation holds only if n>1

[stable temple]

yes

[unreal stump]

So,you split the sum into two parts

Sum of f_n such that n=1 and f_n such that n>1

And the sum of f_n,n>1 part can be rewritten as above(The terms other than sum([n=1]z^n) )

[stable temple]

shouldnt it be sum[f_(n-1) * z^(n-1)] and sum[f_(n-2) * z^(n-2)]?

[unreal stump]

you are splitting
$\sum{f_n z^n}$ as $\sum{f_{n-1} z^n}+\sum{f_{n-2} z^n}$

[vital dew]

MoonBears-D-

[stable temple]

ohhh ok ok i see it now

thanks a lot! :D

[hollow badger]

was wondering if anyone could help me figure out whether im right or wrong ?

all help appreciated

im unsure between answers 2 and 3

[ivory sinew]

Which of those are symmetric?

[hollow badger]

the answers 2

i got it

but thanks

appreciate it

[foggy hatch]

Is there a name/reference for something like "a sequence in a finite alphabet where each term determines the next must be eventually periodic"? This comes up all the time, and I guess is an application of the pigeonhole principle, but I wonder if it has its own name.

[west zenith]

Hum I don't think it has a special name

[toxic bridge]

Should I ask about combinatorics here?

[rough parcel]

Can someone explain this ?

I dont understand what | means

P such that P ?

[quaint star]

Maybe google the Sheffer Stroke

Or look in your notes/book

The stroke is like NAND (not and)

[rough parcel]

I dont have a notes book, I'm in high school.

9th grade

[quaint star]

Okay, well, the Sheffer Stroke is like NAND, like I said

[rough parcel]

Thanks.

[terse crane]

anyone here good at algorithm analysis?

like Big O stuff

[amber hill]

@terse crane yeah I know quite a bit about that, and just post your problem, lmao

[midnight dock]

hi

any idea how i would go about working with such a problem?

[bronze rain]

You have two directions to look at: If the formula is true, conclude the given property of p_i's. And if the given condition on p_i's holds, then the formula is also true.

You can try to look at what each clause of the formula tries to capture and the indices for AND.

[midnight dock]

Im not sure if I've interpreted the notation right but is this it?

[bronze rain]

You also have other clauses in the given formula like (not p_1 or not p_3), (not p_1 or not p_n) which is not clear from what you have written.

As an exercise, you can later try to see how what you have written differs from the other one by finding a condition on the p_i's.

Or at least finding a valuation for the p_i's which satisfies the formula you have written but does not satisfy the other one.

[livid drum]

@midnight dock those double conjunctive products effectively sweep out all distinctive pairs (order notwithstanding) of p’s. Er maybe easier to say like this:
The formula conjuncts over all unordered pairs of distinct propositions.

So let’s do one of the directions in the problem.
Suppose the formula is true.
But Suppose the claim is false. so there are two different true props, say pj and pk.
Now you can go to the formula and expect that one of the conjuncts corresponds to “neg pj or neg pk”. But since both pj and pk is true, this conjunct is false, and so the formula is false. Contradiction.

[stable temple]

are generating functions a general method for solving recurrence relations?

or are there any restrictions on when we can use them?

[obtuse lance]

you can always just write down G(x) and say that its coefficients are the terms of some sequence, but it might not be that useful to use the recurrence relation to get some kind of identity on G to play around with

[stable temple]

ok so im trying to use generating functions to find the asymptotic bounds for fibonacci

so i have

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

and T(n) = T(n-1) + T(n-2) + c

this method of solving the recurrence gives the correct answer for the time complexity as well, but the relation used here doesn't include the + c https://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html

im not sure what to do with the + c

ah, maybe the CS server would be more suitable?

[bronze rain]

You only need to make a small change. Have you tried something?

[pale epoch]

what exactly are you trying to do? solve the recurrence relation or compute the time complexity (of what?)

[obtuse lance]

there's a nice closed form for fibonacci numbers you can get from this that you can derive and use

[stable temple]

find the time complexity of that algorithm above using generating functions

the link i posted uses generating functions to find the closed form for fibonacci numbers

but it solves F(n) = F(n-1) + F(n-2) and my question was that would I use the same process for T(n) = T(n-1) + Tn-2) + c?

c is the constant time for the addition (or whichever operation each iteration takes)

[bronze rain]

Yes

[stable temple]

well, i asked somewhere else and i was also told it'd be the same process

but i dont understand, do i just ignore the + c because we ignore the constants when finding time complexity or what?

[unreal stump]

No

You remember how you can split f_n into n=1 and n>1 cases?

You do the same here

[stable temple]

yes

hm 🤔

[unreal stump]

But T(n)(n>1) splits as T(n-1)+T(n-2)+c

[stable temple]

hmmmmmm

you mean this part?

so, the z is the c?

(from https://www3.cs.stonybrook.edu/~rezaul/Fall-2017/CSE548/CSE548-lecture-7.pdf)

[bronze rain]

Not quite

You should try understanding what is happening and see if you can just modify it slightly by adding another term

[unreal stump]

No,you end up with $\sum{f_{n-1}z^n}+\sum{f_{n-2}z^n}+\sum{cz^n} +\sum{[n=1]z^n}$

[vital dew]

MoonBears-D-

[bronze rain]

Note that z here is just a placeholder and the term generating function is a slight misnomer. In the words of Wilf, 'A generating function is a clothesline on which we hang up a sequence of numbers for display.'

While c is some constant you are dealing with.

If you wish to learn more about generating functions, generatingfunctionology by the guru, Herbert Wilf, is your best friend.

[hollow badger]

yo yo

can a cartesian product have the same properties a relation?

for example could a cartesian product be antireflexive?

[unreal stump]

Cartesian product is a relation

Given sets A and B,define aRb iff a is in A and b is in B

[hollow badger]

yh i realised the stupidity of my question after i asked it

also another thing i wanted to know

if i have a relation R{(1,3) (3,1)(2,4)(4,2)}

would the transitive closure of that relation include (3,3) and (4,4)?

[unreal stump]

Yes

Also (1,1) and (2,2)

[hollow badger]

yh i was sure about those 2 just not about 3 and 4

i didnt know whether an element could only be used once if that makes sense

[weary tiger]

Yeah, because for finite sets it seems that 1) is wrong, but 2) is correct, but for infinite index sets it seems that both statements can be wrong

[weary tiger]

how come? there is no 1 in 2N set

it starts from 2

oh, okay, i see, fair enough

but if i define A_i in such way that they start form n and go to the infinity

so that A_1 = 1, 2 ,3 ,4 ...... and A_2 = 2, 3, 4, 5... and etc

in that case intersection on all A_i will be empty right,

ok, but the stament 2) will still hold right

like trivial case sort of

yes

ok thanks)

[vital dew]

slimvesus

[weary tiger]

that makes sense thanks

[main patio]

can you help me?

ill poast now

[weary tiger]

What do weighted graphs help with?

[quaint star]

There are a lot of problems you can solve with weighted graphs and trying to find the shortest path between two points

Look up traveling salesman problem as an example

[obtuse lance]

you can use it to model transition probabilities between states with discrete time steps

[weary tiger]

Hi Good people's

I hope everything is well and fine at you sides

If any gentleman or woman can help me with Discrete Maths i will appreciate your help and will thank you for showing such act of kindness

[terse crane]

im quite confused

is anyone free to assist

[unreal stump]

Just use Induction

[mint marsh]

My name is Skylar .
I graduated with Mathematics and computer Science majors.
I can help with maths and computer science if needed

[stable temple]

ok im back with the same question now: #discrete-math message

so i thought about it and actually my recurrence relation is:
T(1) = T(0) = c
T(n) = T(n-1) + T(n-2) + c

this is what i have so far

idk how to deal with the sum[T(n-1) * x^(n-1)] term

should i have just left the 2c inside the sum?

[unreal stump]

Change of index

As n varies from 2 to inf,(n-1) varies from 1 to inf

[stable temple]

hmm

i change it to n=1 and subtract T(1)?

[unreal stump]

So,You can rewrite it as sum(T(n)x^n) as n varies from 1 to inf

[stable temple]

oh

but dont i need to bring it to

ahhh ok ok

thanks moonbears i can always count on you :D

[last timber]

hi @unreal stump

are you drake

[unreal stump]

Yes

[frail harness]

hi can u prove this

[unreal stump]

what have you tried?

[frail harness]

i think zero multiplied by anything is zero. that is all what i think

<@&286206848099549185>

[last timber]

have you proved that v = 1*v

and -v = (-1)*v?

(and also have you proved that v+(-v)=0?)

[frail harness]

do i need to prove that because question already says that V is a vector space over the field

is not that explanations of what u all asked for me to prove

[quaint star]

Write 0 as 0+0 and use distributive property

@frail harness

[frail harness]

i know this but i do not know what should i add to complete the solution

[frail harness]

is it part of my proof, should i add this to my solution

[quaint star]

No

You are assuming that your vector space is R^2, and you are assuming what the operation is

You have to prove it over a general vector space, using only the vector space axioms

[frail harness]

"Let V be a vector space over the field F" what specifically should i understand from that? what is the point of saying that it is over the field F? i could not understand the field part

[quaint star]

All vector spaces are over a field

It means your scalars come from that specific field

You can think of it being like R or C (those are examples of fields)

[frail harness]

i am a little bit confused. can u explain the steps so i should prove step by step

[quaint star]

@frail harness do you know the vector space axioms?

[frail harness]

Additive axioms.
Multiplicative axioms.
Distributive axioms

[quaint star]

So, the first step is to say

0v = (0+0)v

Then apply the distributive property, so what do you get?

Every step here is a vector space axiom, except writing 0 as 0+0 which is a field axiom

@frail harness

[stable temple]

ok so i changed the index of the summation to continue from here: #discrete-math message