Solving Linear Homogeneous Recurrence Relations

The famous problems of the towers of Hanoi and Fibonacci rabbits will be used to motivate developing a general theory to solve most linear homogeneous recurrence relations.

To guide the discussion, we will consider your attempted solutions to the 18 exercises in this PDF (click to download) (http://www.cjfearnley.com/MathCounts/LinearHomogeneousRecurrenceRelations.pdf). Strategic note: I feel that exercises 8 and 9 represent the conceptual heart of this topic while exercises 11, 12, and 13 get at the key methods to efficiently solve recurrences. You might want to focus your efforts toward solving 8 and 9. Of course, you will get insights into them by working on the others. All of the exercises attempt to work together to build a coherent story about solving any linear homogeneous recurrence relation (except perhaps #18 which is included as the final exercise in Ma Yu Chun's course on this subject but which may be "too hard" ... I'm not sure yet).

To help you learn the basics about generating functions and recurrence relations, there are 12 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).

The Ma Yu Chun videos are excellent from the perspective that she completely covers her subject. However, there are three challenging aspects to her style: 1) she doesn't repeat herself very often and so you are expected to have mastered each key point that has been previously explained, 2) she expects you to have a basic background in the precalculus topic of solving degree n polynomials including those with complex roots, the binomial theorem in all its various forms, the method of partial fractions, and Taylor expansions from the calculus, and 3) she frequently will foreshadow topics, that is, she will skip steps to give an overview expecting that either you will fill in the gaps on your own or watch each of the next few videos where she will go back and fill in the details.

This is challenging because you have to divine which previous or future concept is skipped at each step. It is my experience that this is precisely the difficulty in all of mathematics: we find it challenging to see all the details all the time. And no one ever includes all the details: that would be a pedantry that no one would value!

My advice: if you have the time and the interest: take up the challenge! Watch the videos multiple times, read my notes multiple times, search for additional resources, look at the other resources highlighted, and post questions in the comment section below. And if you don't have time, wade in with however much time you can put in and you will get a broad overview of an important topic.

Solving the 18 exercises is not necessary to participate, but it will be quite helpful if you can put in at least a bit of effort on most of them so your attempted solutions can help guide our discussion.

• Download and work out these 18 exercises (click here to download the two-page PDF) (http://www.cjfearnley.com/MathCounts/LinearHomogeneousRecurrenceRelations.pdf).

• Recurrence Relation (in Wikipedia) (https://en.wikipedia.org/wiki/Recurrence_relation)

• 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-5, 13-15, and 31-62 are relevant for this topic) for Ma Yu Chun's videos at https://courses.edx.org/c4x/TsinghuaX/60240013.x/asset/EDX_w4.pdf

• Pages 94-100 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=106) provides a good introduction to generating functions. This text may help those who are struggling with some details in the videos below.

• The first five of these 12 Ma Yu Chun videos provide background about generating functions and the problems of the Towers of Hanoi and Fibonacci rabbits. Our focus during the meetup will be on videos 6-12:

• 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. 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

• 3. 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

• 4. 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

• 5. 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

• 6. Definition of linear homogenous recurrence relations, 7 minute video. My notes on week 4, video 7 (https://plus.google.com/104222466367230914966/posts/HgkDzVaAjEw). Subtitles for week 4, video 7 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00007.TSGCMATHT314-V006400_DTH.srt).

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

• 7. Defining the characteristic polynomial of a linear homogeneous recurrence relation, 9 minute video. My notes on week 4, video 8 (https://plus.google.com/104222466367230914966/posts/anoHXTFaB2F). Subtitles for week 4, video 8 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00008.TSGCMATHT314-V006200_DTH.srt).

http://www.youtube.com/watch?v=1eAC7SZ8RAA

• 8. Generating Function And Characteristic Polynomial (the case of distinct roots), 9 minute video. My notes on week 4, video 9 (https://plus.google.com/104222466367230914966/posts/CeKrmtPpLau). Subtitles for week 4, video 9 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00009.TSGCMATHT314-V006000_DTH.srt).

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

• 9. Getting Solution By Characteristic Polynomial (the case of multiple roots), 11 minute video. My notes on week 4, video 10 (https://plus.google.com/104222466367230914966/posts/GxL33b3LNmu). Subtitles for week 4, video 10 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00010.TSGCMATHT314-V005800_DTH.srt).

http://www.youtube.com/watch?v=61Z8zD5gKvk

• 10. Getting Solution By Characteristic Polynomial (the case of complex roots), 8 minute video. My notes on week 4, video 11 (https://plus.google.com/104222466367230914966/posts/MafnSGvGdz2). Subtitles for week 4, video 11 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00011.TSGCMATHT314-V005600_DTH.srt).

http://www.youtube.com/watch?v=7SH0fEadNQU

• 11. Example (1), 8 minute video. My notes on week 4, video 12 (https://plus.google.com/104222466367230914966/posts/SihcmxSZmHD). Subtitles for week 4, video 12 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00012.TSGCMATHT314-V005200_DTH.srt).

http://www.youtube.com/watch?v=yO-kzWqzNTQ

• 12. Example (2), 8 minute video. My notes on week 4, video 13 (https://plus.google.com/104222466367230914966/posts/DnHBA22ChTF). Subtitles for week 4, video 13 (http://cjfearnley.com/TsinghuaX60240013.x/week4/Week4.00013.TSGCMATHT314-V005400_DTH.srt).

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

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 fifth 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 the first session, see Combinatorics: The Science of Counting and Arrangements (19 Sep 2015) (https://www.meetup.com/MathCounts/events/224748900/). For the second session and its problem set see Combinations and Permutations (28 May 2016) (https://www.meetup.com/MathCounts/events/230843893/). For the third session and its problem set see Counting with Generating Functions (Integer Partitions and more) (22 Oct 2016) (https://www.meetup.com/MathCounts/events/234687256). The fourth session and its problems set are at Solving Basic Recurrence Relations with Generating Functions (28 Jan 2016) (https://www.meetup.com/MathCounts/events/lcrdlmywcblc/).