# Tag Info

9

One thing that you have to keep in mind here, is that you don't need to understand recursion to implement it. There is a big difference between "we were taught to do it like that, I implement it and it works" and really understanding the concepts and why it works as it does. With induction, on the other hand, you are supposed to write down a complete, formal ...

5

My philosophy is schedule über alles. As an academic, time is your most constrained resource. This goes for balancing the hours in your work vs. research, teaching, and service requirements. And in this case it goes for the limited number of class sessions in your semester. Do you not have a day-by-day schedule for your term? You should. For me, it's the ...

4

As a disclaimer, I am a CS teacher, so I teach both concepts within that context. However, there is no doubt in my mind that induction is far harder for students to grasp. I have not been able to figure out why. Part of the problem with induction is that there are simply so many moving parts. The inductive step can be quite complex (particularly in my ...

4

I am inclined to choose the last one. Maybe the majority have a different feeling about the lecture. If you run a survey and the majority of students "thought the last lecture was too difficult", that won't necessarily be because they already know linear algebra and would have found a vector space perspective easier to understand. It is possible ...

3

I liked this Discrete Mathematics: An Open Introduction, by Oscar Levin, for generating functions, so I'm guessing it will be good for recurrence relations.

2

After looking at Tony Jacobs argument, here is an argument of my own. Start with a single male. At each generation, let $m_n$ and $f_n$ be the total number of males and females respectively, and let $s_n=m_n+f_n$. We have $$f_0=0, f_1=1, m_0=1, m_1=0.$$ Since each male comes from a female from the previous generation, we have  \tag{1}m_{n+1}=f_n,\ \ \...

2

You can see it by breaking the numbers $s_n$ into parts: $s_n=f_n+m_n$, which represent the number of female and male bees, respectively, at each level of the family tree. To find $f_{n+1}$, we note that each female bee at level $n+1$ is either the mother of a female bee at level $n$, or else the paternal grandmother of a female bee at level $n-1$. This is ...

2

In the context of programming, it seems more natural to distinguish recursion from iteration than from induction, as iteration is the algorithmic realization of iteration. In the context of mathematical proof, recursion becomes something like the method of infinite descent (e.g. the classic proof of the irrationality of $\sqrt{2}$), and is quite natural ...

1

Better yet, I very much liked generatingfunctionology by Herbert Wilf; it is the go-to text for what you are seeking. It addresses generating functions, and considerable help for understanding recurrence relations. (And it's free from the author, and downloadable as a pdf.!) In addition, you'll find extensive information at Ronald L. Graham, Donald E. ...

Only top voted, non community-wiki answers of a minimum length are eligible