Basic Problemscountinglinear

Lucas Numbers

Return the nth Lucas number, a sibling sequence to Fibonacci that starts 2, 1 and again sums the two previous terms. The first few terms run 2, 1, 3, 4, 7, 11.

Do this lesson first: climbing stairs

Example input

n = 8

Expected output

47

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = dp[i - 1] + dp[i - 2]

Ask what the last term added, the same question Fibonacci asks. Position i is defined as the sum of the two positions before it, so there is exactly one way to reach it and both predecessors contribute. The recurrence is identical to Fibonacci's; only the two seeds that start it differ, which is why every Lucas number can also be written as a sum of two Fibonacci numbers.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 2 and dp[1] = 1 are given by definition, and they are the only difference from Fibonacci; they cannot be derived. Every other cell depends only on smaller indices, so filling left to right guarantees both dependencies exist before they are read.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

2

1

3

4

7

11

18

29

47

lucas-numbers.ts

1function lucas(n) {
2 const dp = [2, 1];
3 for (let i = 2; i <= n; i++) {
4 dp[i] = dp[i - 1] + dp[i - 2];
5 }
6 return dp[n];
7}

Base caseComputedBeing readAnswer

The code, the trap, the variations

lucas-numbers.ts

1function lucas(n) {
2 const dp = [2, 1];
3 for (let i = 2; i <= n; i++) {
4 dp[i] = dp[i - 1] + dp[i - 2];
5 }
6 return dp[n];
7}

Where people go wrong

Reusing Fibonacci's seeds by habit. Starting this recurrence at 0, 1 instead of 2, 1 produces the Fibonacci sequence itself, term for term, since the two sequences share a recurrence but not a starting point. The seeds are the only thing this problem asks you to get right.

Start the same recurrence from 0, 1 instead of 2, 1.
That is Fibonacci itself: identical recurrence, identical order, only the two seeds change.
Sum the three before it instead of the two, with a third seed added to match.
A third bucket joins the sum and a third base case is needed, the same jump that turns Fibonacci into Tribonacci; the left-to-right order stays the same.

Tribonacci Numbers Climbing Stairs