《具体数学》Lesson 1：Recurrent Problem学习笔记

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162397627

Recurrent Problem 递归问题

Mathematical Induction 数学归纳法

Every recurrence problem can be divided into 3 parts :
(1) Research on the small situations
(2) Give the recurrence relation （递归式）
(3) Make the closed-form （封闭形式）

Mathematical induction = Basis + Induction

We first assume the closed-form (3) is right for $n-1$ , and we use the recurrence relation (2) to proof the $n$ is also right. Apparently, the boundary is the small situations (1)

Example : The Tower of Hanoi

Recurrence relation :

Close-form：

Example：Lines in the plane

Recurrence relation:

Close-form:

Example: The Josephus Problem

Recurrence relation:

Close-form:

Binary & Rotate

Binary in Josephus Problem

Consider the Josephus Problem, if we write $n$ in base-2 notation :

And finally we find that:

So $J(n)$ is $n$ rotate left by one bit .

Rotate

Thurthermore, we can solve all the recurrent problem in this bit. For:

We can find that:

The main varibles are d and c .

Repertoire method 成套方法

To solve the common problem: (We need its close-form)

We can assume that:

$$f(n)=A(n)\alpha + B(n)\beta + C(n)\gamma$$

Then we have 2 ways:

• Way 1 : We solve $A(n), B(n), C(n)$ separately, using the method Mathmatical Induction

• Way 2 : Use Particular solution to make Equation

For each particular solution, we can substitute to know the particular paremeter , then we get an equation of A(n),B(n),C(n)

The numbers on particular solution we need equals to the numbers of paremeters

---

For example, in Josephus Problem, if we substitute 3 particular solution:

• $\alpha = 1, \beta = \gamma = 0$ , this particular solution enables us to know the closed-form of $A(n)$

• $f(n)=1$

• $f(n)=0$

And we get the equations:

As we know the closed form of $A(n)$ , we can solve fot $B(n),C(n)$