Generating Functions -- Number Theory 29

[@lucaarmstrong6375]

Great Video! Generating functions are one of my favourite topics in number theory

[@hansolo9892]

Generating functions is not a topic of number theory. It is more diverse. It goes in almost all fields of math as a very decent functioning tool.

[@DinHamburg]

the remark on the lower left side of the board (complex numbers - modular forms) haunts me - can you please make a video which shows some intro/overview on what is to be expected there and how it works?

[@stewartcopeland4950]

Excellent subject ! @23:45 q/(1- q - q^2 ) = - q/(q^2 + q -1 +5/4 - 5/4) = - q/((q + 1/2)^2 - 5/4 ) = - q/(q + 1/2 + 5^0.5/2)(q + 1/2 - 5^0.5/2) = q/5^0.5 (1/(q+ phi) -1/(q + phi')) with phi = golden number and phi' its "conjugate"; after a factorization to use geometric series formula, we find the famous expression: fn = (1/5^0.5)(phi^n - phi'^n)

[@divergentmaths]

Be careful. At 11:35 you have implicitly assumed the stability of the series. All Lucas & Fibonacci series are stable, so it worked fine here. But if you do the same move on an unstable series (such as the monotonic divergent series of natural numbers) you will get to an incorrect result.

[@housamkak8005]

You do not really care about convergence or divergence when working with formal series, you can manipulate those objects without worrying about them being analytical. If they were analytical then great bonus, if not, it is just an algebraic manipulation as the polynomial is just a placeholder of our sequence.

[@TimFSpears]

HW1: I get to G(q)=(3q^2 + 2q + 1)/(1 - q^3) but I can’t get that back to the closed form to make it useful. I would have to guess that the closed form would include a modulo operation and don’t see where that will come from. Perhaps this is as far as we can go with this exercise? a sub n = n % 3 + 1

[@MathFromAlphaToOmega]

I think it might be interesting if you had a few introductory videos on modular forms. Even if you don't get into all the details, you could show some examples of the identities that can be proved with them.

[@r.maelstrom4810]

First HW exercise: The generating function sequence is equal to (1 + q^3 + q^6 + q^9 +...) + (2q + 2q^4 + 2q^7 + 2q^10 +...) + (3q^2 + 3q^5 + 3q^8 + 3q^11 +...) = [1/1-q^3] + [2q/1-q^3] + [3q^2/1-q^3].

[@梁偉康-d9k]

Vujc

[@tylercrowley2559]

Would you be able to find a closed form for a_n given this generating function?

[@vietdungle1237]

​@@tylercrowley2559 a_n = 1 as n = 3k 2 as n = 3k + 1 3 as n = 3k + 2 (k is an integer) Well, the definition is its own closed form pretty much

[@leif_p]

To check your work on the second warm-up, here are the first few terms: 3, 10, 32, 99, 301, 908, 2730

[@IanXMiller]

Here is my answer which does generate these terms. Spoiler: aₙ=15/4•3ⁿ - n/2 - 3/4

[@synaestheziac]

@@IanXMiller do you remember what you got for the generating function for the second warmup? I got (12q^2-23q+10)/[(1-q)^2*(1-3q)], but based on your final answer I probably messed something up…

[@IanXMiller]

@@synaestheziac Your denominator is right. Numerator should be 3q²-5q+3

[@АндрейВоинков-е9п]

First HW: you can get 3 first items out of sum, and then fix the sum to make it equal to original, but with q^3 multiplier

[@panPetr0ff]

Nice introduction! Generating functions seem to be very powerful tool. I am not able to solve the SUM/0->inf/ A(n) ...where A(0)=1 and A(n) = A(n-1) (3/(2n) - 1) So will it be possible to get the result by using GF ?

[@IanXMiller]

Thanks for this question. It was a challenging problem to try after Michael's homework question to make sure I really understood how to do these. With the n in the denominator you do it similar to how Michael did the n+1 but you need to look at it being the integral of qⁿ⁻¹ (rather than the derivative like in his example). You can manipulate it and take a derivative to remove the integral to get A(q)=2(1+q)A'(q), A(0)=1. Solving this differential equation gives A(q)=sqrt(1+q) and applying McLaurin techniques turns this into a polynomial with coefficients: aₙ = (2n)! / ((2n-1) (-4)ⁿ (n!)²). For the last step, finding the sum, simply note that your sum is A(1) = √2.

[@wannabeactuary01]

At 4:00 does 0

[@romajimamulo]

Yeah, we assume that things always converge if it's possible for them to

[@ConManAU]

It’s weird, but since we never actually use them value of q anywhere all that matters is that it converges somewhere.

[@yoav613]

You do not look for convervence you just want to find an

[@محمودابوعلي-ش8س]

great lesson , thank you very much ❤

[@cheems1337]

Wow. How come I never learned that, it seems really useful

[@willnewman9783]

I feel like it is important to phase that 1/(1-q) is literally equal to 1+q+q^2+... To me, it seems like you are suggesting that we just use the notation of 1/(1-q) for shorthand. But later in the video, you are using the fact that this is an equality, not just a shorthand, when you are solving for the closed forms.

[@hydraslair4723]

If you suppose that the sum of sequence a sub n converges, then A(1) gives the sum of the sequence, the result of the infinite series. For sequences that surely cannot have a convergent sum, like (n+1)2^n, this still works but gives a weird result (for (n+1)2^n, it comes out 1). What is this value? Does it have any relevance?

[@wannabeactuary01]

Brilliant - thank you!

[@weilam]

24:39 Good place to stop

[@goodplacetostop2973]

Missed opportunity to mention 19:00 on Fibonacci day 😭😭😭

[@michaelempeigne3519]

I was doing it and got a different answer : a_n = (7 / 5 ) * 5^n -( 2 / 5 ) * ( - 5 )^n for the sequence a_0 = 1 and a_1 = 9.

[@renyxadarox]

Find a closed form of generating function for the sequence aₙ=aⁿ^², n∈N, |a|

[@tirthankarsingh8776]

Thanks a lot 😀 watched your content first time.it was amazing

[@shafikbarah9273]

What about the sequence a_n = n what's its function?

[@Alex-fh4my]

for the sequence 1,2,3,4,5 ... the generating function is 1/(1-x)^2, which is the derivative of 1/(1-x) which has sequence, 1,1,1,1...

[@evenaicantfigurethisout]

i think it might be a good idea to put a link to the playlist "Number Theory" in the description for the uninitiated. 😉

[@CM63_France]

Hi, 23:41 : bizarre, this will not give us the characteristic equation for the golden ratio... For fun: 1:04 , 3:41 , 4:31 , 6:47 , 10:45 , 24:13 : "and so on and so forth", 8:23 : "great", 13:12 : we don't worry.

[@TimFSpears]

That’s because the expression you have derived then needs to be rewritten in the form sum n>=0 (a sub n * q^n). Then the a sub n expression will be the familiar formula.

[@wolframhuttermann7519]

By the the way, sequences added relativistically are a horror. For more information see this link: en.wikipedia.org/wiki/Velocity-addition_formula#Special_relativity

[@guruji75]

Thank you…

[@zawodnikgrajacywosupochodz2589]

My birthday!!!

[@ZainAlAazizi]

This is the base of the so-called Z-Transform 😁

[@titan1235813]

Hello, Michael 👋🏻

[@stmmniko7836]

?

[@reinerwilhelms-tricarico344]

Convergence? Who cares ;-)

[@ZeroG]

this is clearly wrong. 1+q^2 +q^3... is infinity, not 1/(1-q) which makes zero sense whatsoever

[@DendrocnideMoroides]

you are partially correct the formula 1+q^2+q^3=1/(1-q) only works for -1