tag:blogger.com,1999:blog-391332808443807350.post8012467867903536521..comments2020-11-20T03:03:44.658-05:00Comments on gtMath: Recursions Part 2: Generating Functionsgtmathhttp://www.blogger.com/profile/17592451309514283248noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-391332808443807350.post-72163525593485928642015-07-15T02:06:27.036-04:002015-07-15T02:06:27.036-04:004) There is already a formula for the coefficients...4) There is already a formula for the coefficients of a Fourier series, but once again there is a connection in that the Fourier series basically divides a function into its constituent single-frequency signals. There is also a similarity between solving differential equations using integral transforms and solving recurrences using generating functions: in both cases, we turn the problem into an algebraic one which is easier to solve and then extract the answer we were looking for.gtmathhttps://www.blogger.com/profile/17592451309514283248noreply@blogger.comtag:blogger.com,1999:blog-391332808443807350.post-30118835735832088592015-07-15T01:47:41.060-04:002015-07-15T01:47:41.060-04:003) You're exactly right: partition functions a...3) You're exactly right: partition functions are very similar in the sense that they sort of store a bunch of information we want, which we can extract by taking derivatives or extracting coefficients of the series. Thus partition functions are a type of generating function. To the second part of your question, I wouldn't say the generating function of a recurrence has an expected value since the coefficients aren't probabilities. If you take the derivative of an OGF, you get a new recurrence with the terms shifted over and multiplied by their index ($n$ value) from the old recurrence- can you see why?gtmathhttps://www.blogger.com/profile/17592451309514283248noreply@blogger.comtag:blogger.com,1999:blog-391332808443807350.post-67081880104702456852015-07-15T01:25:38.839-04:002015-07-15T01:25:38.839-04:00(breaking my answer into a few replies here...)
2)...(breaking my answer into a few replies here...)<br />2) Yes, exactly- to "solve" a recurrence means to find a formula for the $n$-th term which depends on $n$, but not on any of the earlier terms- in other words, to eliminate the self-referential nature as you put it.gtmathhttps://www.blogger.com/profile/17592451309514283248noreply@blogger.comtag:blogger.com,1999:blog-391332808443807350.post-64110739542914295052015-07-15T01:22:53.740-04:002015-07-15T01:22:53.740-04:00Good questions.
1) I am having trouble finding the...Good questions.<br />1) I am having trouble finding the full story for the Binet formula above (honestly, I just copied that fact from where I was reading about the formula and didn't really investigate it further), but upon seeing your question, I looked into it and found a full history of the development of the Catalan numbers also mentioned above. These are some of the most prolific in combinatorics; it turns out that many famous mathematicians including Euler were working on problems in which these numbers arose as early as the mid-18th century, in various countries, and sometimes collaborating via letters. Igor Pak wrote a good summary of this history, to which I have now added a link in the post above- check it out. If you go onto his page on the UCLA math website, he even has links to the letters he mentions, which are in German, French, and Latin, some with English translations. Pretty cool to see Euler's handwriting (it's pretty much impossible to read, but still)...gtmathhttps://www.blogger.com/profile/17592451309514283248noreply@blogger.comtag:blogger.com,1999:blog-391332808443807350.post-70019478807948176642015-07-09T03:15:07.355-04:002015-07-09T03:15:07.355-04:001)What does it mean to "rediscover math"...1)What does it mean to "rediscover math"? Like did *nobody* remember that Euler wrote that paper and then Binet was just the first person to find it again? Or did sincerely think he was being original?<br />2) It's a little unclear to me what you mean when you say you are "solving" the recursion. Does that just mean you are taking the already nifty equation we have and making it even niftier by by eliminating its self-referential nature?<br />3) Generating functions are really cool. We use them a lot in physical chemistry too (for statistical mechanics). You probably used them in physics as well. But we called them "partition functions". Conceptually, it seems very similar: the sum of all states. But can you also use these partition functions as generating functions? That is to say, we would often take partial derivatives of our generating function to calculate expected values. Is there some sort of expected value for these recursions?<br />4) This also looks pretty similar to my good buddy, Fourier, and my slightly less good buddy, Laplace. Can we use generating function techniques to find the coefficients for those series?<br />As always, some very cool stuff from G T Math. I look forward to reading the next one :DAnonymoushttps://www.blogger.com/profile/02286537588071656226noreply@blogger.com