13.9. Conclusion and Summary

In this lecture, we introduced a new counting method called counting by recurrence equations. We discussed how this method can simplify many counting problems, especially in discrete mathematics and computer science.

In the lecture, students learned that counting problems can often be solved more easily by using recurrence equations. These equations allow us to express a counting problem in terms of smaller subproblems, making it easier to find solutions. Recurrence equations are particularly useful when the problems can be defined recursively, similar to the way the Fibonacci sequence is defined, where to find the nth term, you rely on the previous two terms.

Think of a family tree. To understand how many ancestors you have (like grandparents versus great-grandparents), you can use the idea of counting: each person has two parents. Thus, as you go up the family tree, the number of ancestors can be calculated recursively. This is similar to how recurrence equations work.

We discussed a very simple method of solving linear equations called the iterative method, along with forward and backward substitutions.

The iterative method involves rewriting the recurrence relation multiple times until a pattern emerges. The forward substitution means starting with initial conditions and substituting step-by-step to find higher terms, while backward substitution means starting from the established pattern and rewriting it to express earlier terms in terms of known values. Both methods aim to derive a closed-form solution that is easier to compute than going sequentially through each term.

Consider baking a cake. If the recipe says to bake for 30 minutes at 350°F, you can think of each minute as a step in a sequence. Instead of just counting minutes, if you note how the cake rises at each 5-minute interval (like writing down the height every 5 minutes), you will create a pattern. Recognizing that pattern (or the relationship between the increments) allows you to determine when the cake will be fully baked without counting every minute.

We also discussed about an important category of recurrence equations namely linear homogenous recurrence equations of degree n with constant coefficients.

Linear homogeneous recurrence equations are a specific type of recurrence relation where the next term is defined as a linear combination of previous terms, and there are no additional variables that distort the equation. The degree of the equation refers to how many previous terms are taken into account. For example, in the Fibonacci sequence, each term is the sum of the two preceding terms, which is a linear homogeneous equation of degree 2.

Imagine you are publishing a weekly newsletter. The number of subscribers today is the sum of the number of subscribers from the last two weeks. If last week you had 100 subscribers and the week before that you had 80, the current total would simply be 100 + 80 = 180. This method mirrors how linear homogeneous equations operate, relying solely on previous values.

To summarize, this lecture focused on counting by recurrence equations and solving methods including linear homogeneous equations.

The conclusion emphasizes key takeaways from the lecture. Students learned not only about how counting can be simplified through recursion but also gained insights into specific methods for solving these recurrence relations. The iterative methods were emphasized as practical tools for students tackling problems in discrete mathematics and computer science.

Think of a roadmap when trying to drive from point A to point B. If you take different routes (methods), but the destination remains the same (solved problem), it illustrates the different approaches we can take to get the same answer in mathematics – just like using recursion.

--