search

Tag - Recurrences

The Drunkard's Walk Wed, Oct 17, 2018 02:00 CEST

A drunkard is zigzagging home. At every steps forward (or backward) he is making, he also moves $$1$$ step to the left with probability $$p$$ and $$1$$ step to the right otherwise. He starts $$i$$ steps to the right of a river. What is the expected number of steps forward before he falls into the river?

Recurrences Sat, Apr 22, 2017 02:00 CEST

Theorem

Let $$a \in \mathbb{N}$$, $$t < a \in \mathbb{N}$$, and $$b \in \mathbb{R}$$. Defining $$A_t$$to be some real number and

$$A_N = (1 - \frac{a}{N}) A_{N-1} + b, N > t \in \mathbb{N},$$

then

$$A_N = \frac{b}{1+a} (N+1), N \ge a \in \mathbb{N}.$$

Fibonacci numbers Mon, Jun 29, 2015 02:00 CEST

The Fibonacci numbers are defined as $$f_0 = 0,\ f_1 = 1$$ and, for $$i \ge 2,\ f_i = f_{i-1} + f_{i-2}$$. Here is the beginning of the Fibonacci sequence:

$$0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots$$

We generalize the definition above by changing the two initial values, for example with $$f_0 = 4,\ f_1 = 6$$ we obtain

$$4, 6, 10, 16, 26, 42, \ldots$$