MathDB
Show that 2^n < f(n) ≤ 4 . 3^(n-1) - [Canada MO 1979 - P5]

Source:

September 29, 2011

Problem Statement

A walk consists of a sequence of steps of length 1 taken in the directions north, south, east, or west. A walk is self-avoiding if it never passes through the same point twice. Let f(n)f(n) be the number of nn-step self-avoiding walks which begin at the origin. Compute f(1)f(1), f(2)f(2), f(3)f(3), f(4)f(4), and show that 2n<f(n)≤4⋅3n−1.2^n < f(n) \le 4 \cdot 3^{n - 1}.
Back to ProblemsView on AoPS