Introduction

The Pell(no, not Bell) Numbers are a simple, Fibonacci-like sequence, defined by the following relation:

$P_n=\begin{cases}0&\mbox{if }n=0;\\1&\mbox{if }n=1;\\2P_{n-1}+P_{n-2}&\mbox{otherwise.}\end{cases}$

They also have a closed form:

$P_n=\frac{\left(1+\sqrt2\right)^n-\left(1-\sqrt2\right)^n}{2\sqrt2}$

And a matrix multiplication based form, for the daring:

$\begin{pmatrix} P_{n+1} & P_n \\ P_n & P_{n-1} \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}^n.$

Challenge

Your mission, should you choose to accept it, is to do any one of the following:

1. Given $n$, calculate the $n^{th}$ term of the sequence (0 or 1-indexed).

2. Given $n$, calculate the first $n$ elements of the sequence.

3. Output the sequence indefinitely.

Scoring

This is code-golf. Shortest answer in each language wins.

posted almost 4 years ago

CC BY-SA 4.0

4y ago

Razetime‭

2860 reputation 42 65 321 83