Discussion

Yolanda took a sip of coffee I'm glad I paid attention when we were studying vector spaces, bases, and dimension. All this stuff about solutions for recurrence equations made complete sense. And I can really understand why the professor was making a big deal out of factoring. We saw it our first semester when we were learning about partial fractions in calculus. And we saw it again with the differential equations stuff. Isn't it really neat to see how it all fits together? All this enthusiasm was too much for Alice who was not having a good day. Bob was more sympathetic, saying Except for the detail about zero as a root of an advancement operator polynomial, I was ok with this chapter. Xing said Here we learned a precise approach that depended only on factoring. I've been reading on the web and I see that there have been some recent breakthroughs on factoring. Bob jumped back in But even if you can factor like crazy, if you have a large degree polynomial in the advancement operator equation, then you will have lots of initial conditions. This might be a second major hurdle. Dave mumbled Just do the factoring. The rest is easy. Carlos again was quiet but he knew that Dave was right. Solving big systems of linear equations is relatively easy. The challenge is in the factoring stage.

Despite thinking the material of this chapter was interesting, Bob also wondered if they really needed all of this machinery. Defining a recursive function is easy in almost all programming languages, so why not just use a computer to calculate the values you need?The history of how recursion made its way into ALGOL (and therefore most modern programming languages) involved some intrigue. Maarten van Emden recounts this in a blog post entitled How recursion got into programming: a tale of intrigue, betrayal, and advanced programming-language semantics. Xing started to remark that the techniques of this chapter could provide a good way to understand the growth rate of recursive functions in terms of the big Oh notation of , but Alice interrupted to propose a programming experiment as something that would raise her spirits. (The chance to prove Bob wrong was probably more motivational than the chance to do some coding, but she didn't want to be too mean.)

The group decided to take a look at the recurrence in , which they immediately wrote as a recursive function defined on the nonnegative integers by \[\begin{aligned}\end{aligned}\] Alice grabbed her computer and implemented this in SageMath and computed a few test values.

She then defined a second function s that was the explicit (nonrecursive) solution from and checked that values matched.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.