Solving Basic Recurrence Relations with Generating Functions

This discussion will explore a way of using generating functions (https://en.wikipedia.org/wiki/Generating_function) (a generalization of polynomials and power series that proves to be a very powerful counting tool) to find closed-form expressions (https://en.wikipedia.org/wiki/Closed-form_expression) for certain kinds of recurrence relations. First the basic definition of generating functions will be developed. Then the famous problems of the towers of Hanoi and Fibonacci rabbits will be used to produce elementary recurrence relations which can be solved using the method of generating functions.

To guide the discussion there is an 11 question exercise set (click here to download the PDF) (http://www.cjfearnley.com/MathCounts/GeneratingFunctionsFibonacci.pdf).

To help you learn the basics about generating functions and recurrence relations, there are 8 highlighted Ma Yu Chun videos from the free on-line course TsinghuaX 60240013.x Combinatorial Mathematics (https://www.edx.org/course/combinatorial-mathematics-tsinghuax-60240013x-0) on the edX (http://edx.org) platform (Note: in Wikipedia it is reported that Tsinghua University (https://en.wikipedia.org/wiki/Tsinghua_University) is sometimes called the "MIT of China" due to its specialty in engineering and science).

Since Ma Yu Chun can be difficult for some people to understand, I have written detailed notes for each video and subtitles for the videos are available. I recommend watching each video for the first time at a slow playback speed (maybe 70-90% of full speed). As with reading a mathematics paper, it can be helpful to watch the videos once to get an overview before taking notes and studying the video to master the key points. Searching for additional resources may be necessary to supplement the videos.

• Download and work out 11 exercises (click here to download the one page PDF) (http://www.cjfearnley.com/MathCounts/GeneratingFunctionsFibonacci.pdf).

• Download 48 pages of slides (only pages 1-12 and 35-48 are relevant for this topic) for Ma Yu Chun's videos at https://courses.edx.org/c4x/TsinghuaX/60240013.x/asset/edxCM_w3.pdf

• Download 62 pages of slides (only pages 1-6 and 13-14 are relevant for this event) for Ma Yu Chun's videos at https://courses.edx.org/c4x/TsinghuaX/60240013.x/asset/EDX_w4.pdf

• 1. Definition Of Generating Function (1), 10 minute video. Read my notes on video 1 (https://plus.google.com/104222466367230914966/posts/4ATWakKuiDZ). Subtitles for video 1. This video assumes an understanding of the product and sum principles of counting. For a refresher in understanding these principles, read my notes on Ma Yu Chun's 9 minute video introduction to the fundamental principles of counting (https://plus.google.com/104222466367230914966/posts/TqtbKxzLVgz).

http://www.youtube.com/watch?v=zolnm0zTx40

• 2. Definition Of Generating Function (2), 8 minute video. Read my notes on video 2 (https://plus.google.com/104222466367230914966/posts/NRFW7nookEc). Subtitles for video 2.

http://www.youtube.com/watch?v=Vc5LsbLl0cI

• 3. What Can We Do With A Generating Function?, 4 minute video. Read my notes on week 3, video 8 (https://plus.google.com/104222466367230914966/posts/GuejZuNKK5C). Subtitles on week 3, video 8 (http://cjfearnley.com/TsinghuaX60240013.x/week3/Week3.00008.TSGCMATHT314-V003300_DTH.srt).

http://www.youtube.com/watch?v=KkH0U2SEev4

• 4. The Towers of Hanoi, Part 1, 4 minute video. Read my notes on week 3, video 9 (https://plus.google.com/104222466367230914966/posts/hynE2kTSNFL). Subtitles on week 3, video 9 (http://cjfearnley.com/TsinghuaX60240013.x/week3/Week3.00009.TSGCMATHT314-V003600_DTH.srt).

http://www.youtube.com/watch?v=BvdFMPYYZU0

5. The Towers of Hanoi, Part 2, 10 minute video. Read my notes on week 3, video 10 (https://plus.google.com/104222466367230914966/posts/QCVs2913iTA). Subtitles for week 3, video 10 (http://cjfearnley.com/TsinghuaX60240013.x/week3/Week3.00010.TSGCMATHT314-V003900_DTH.srt).

http://www.youtube.com/watch?v=te5LQjJybHo

• 6. Summary of week 3, 3 minute video. Read my notes on week 3, video 11 (https://plus.google.com/104222466367230914966/posts/ghdg1A7ypiC). Subtitles for week 3, video 11 (http://cjfearnley.com/TsinghuaX60240013.x/week3/Week3.00011.TSGCMATHT314-V004100_DTH.srt).

http://www.youtube.com/watch?v=te5LQjJybHo

• 7. Introduction to the Fibonacci sequence, 9 minute video. Read my notes on week 4, video 1 (https://plus.google.com/104222466367230914966/posts/SNiqL6fbkNz). Subtitles for week 4, video 1 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00001.TSGCMATHT314-V007800_DTH.srt).

http://www.youtube.com/watch?v=yB0ICHhjbpA

• 8. A closed-form expression for Fibonacci numbers, 8 minute video. Read my notes on week 4, video 4 (https://plus.google.com/104222466367230914966/posts/LH7ffbxfZjK). Subtitles for week 4, video 4 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00004.TSGCMATHT314-V007000_DTH.srt).

http://www.youtube.com/watch?v=a3C8DdP6xFE

• (Optional) Pages 81-94 of Kenneth P. Bogart's free on-line resource "Combinatorics Through Guided Discovery" (http://www.math.dartmouth.edu/news-resources/electronic/kpbogart/ComboNoteswHints11-06-04.pdf#Page=93) provides a good introduction to generating functions.

https://upload.wikimedia.org/wikipedia/commons/f/f3/Straight_line.png

I use the python script youtube-dl to download the videos. You can download the latest version at https://rg3.github.io/youtube-dl/ . Youtube-dl should work on any system that supports python.

If you download the subtitles to the same directory as the videos, in Linux you can use "mplayer -sub SUBTITLES-FILE VIDEO-FILE" or "mpv --sub-file SUBTITLES-FILE VIDEO-FILE" where SUBTITLES-FILE and VIDEO-FILE are the local names you gave to those files.

https://upload.wikimedia.org/wikipedia/commons/f/f3/Straight_line.png

Note: this is our fourth session on Ma Yu Chun's course Combinatorial Mathematics (https://www.edx.org/course/combinatorial-mathematics-zu-he-shu-xue-tsinghuax-60240013x-0). To see the event description and problem set from previous sessions, click on the link. The first session: Combinatorics: The Science of Counting and Arrangements (19 Sep 2015) (https://www.meetup.com/MathCounts/events/224748900/), the second session: Combinations and Permutations (28 May 2016) (https://www.meetup.com/MathCounts/events/230843893/), the third session: Counting with Generating Functions (Integer Partitions and more) (22 Oct 2016) (https://www.meetup.com/MathCounts/events/234687256).