2. Suppose you have a row of n + 1 lilypads, and Fred wants to jump on every one of them exactly

once. At each jump, he is able to jump one lilypad forward, one lilypad backwards, or two

lilypads forward (skipping one). Let f(n) denote the number of ways Fred can jump on each of

the n + 1 lilypads, starting at the first lilypad and ending at the n+1th lilypad.

(a) (0.5 marks) What are the first six terms in this sequence, starting with f(0)?

(b) (2 marks) Give a recursive formula for f(n). Briefly justify why your formula is correct.

What is another name for this sequence?