Analysis of Algorithms Week 3

这次回顾第三周的内容。

课程主页:https://www.coursera.org/learn/analysis-of-algorithms

Exercise

3.20

Solve the recurrence $a_{n}=3 a_{n-1}-3 a_{n-2}+a_{n-3} \text { for } n>2$ with $a_0=a_1=0$ and $a_2=1$.

首先对原式进行改写:

那么

3.28

Find an expression for $\left[z^{n}\right] \frac{1}{\sqrt{1-z}} \ln \frac{1}{1-z}$.

Hint. Expand $(1-z)^{-\alpha}$ and differentiate with respect to $\alpha$.

两边关于$\alpha $求导可得

取$\alpha =\frac 1 2$可得

Problem

1

Which of these sequences is represented by the OGF $\frac 3 {1-z}$?

  • 0, 0, 1/2, 0, 1/4, 0, 1/6, …

  • 1, 3, 9, 27, 81, 243, …

  • 3, 3, 3, 3, 3, …

  • 1, 1 + 1/2, 1 + 1/2 + 1/3, …

  • 0, 0, 1, 3, 6, 10, …

解:

所以

2

Suppose that $a_{n}=9 a_{n-1}-20 a_{n-2}$ for $n>1$ with $a_{0}=0$ and $a_{1}=1 .$ What is the value of
$\lim _{n \rightarrow \infty} a_{n} / a_{n-1} ?$

首先对原式进行改写:

那么

因此

3

What is the value of $\sum_{0 \leq k \leq n}\left(\begin{array}{c}{2 k} \ {k}\end{array}\right)\left(\begin{array}{c}{2 n-2 k} \ {n-k}\end{array}\right) ?$

解:记

那么

因为

所以