Công thức truy hồi và phần cơ sở

**Phần cơ sở** cho giá trị ở trường hợp đầu tiên. **Công thức truy hồi** tính trường hợp sau từ các trường hợp trước. Chỉ biết quy tắc mà thiếu cơ sở thì chưa xác định được dãy cần tính. Ba dãy dưới đây đánh chỉ số từ 0; công thức ở cột cuối áp dụng với $n\ge2$. | Dãy | Phần cơ sở | Công thức truy hồi | |---|---|---| | Fibonacci | $F_0=0,\ F_1=1$ | $F_n=F_{n-1}+F_{n-2}$ | | Lucas | $L_0=2,\ L_1=1$ | $L_n=L_{n-1}+L_{n-2}$ | | Pell | $P_0=0,\ P_1=1$ | $P_n=2P_{n-1}+P_{n-2}$ | Fibonacci và Lucas có cùng quy tắc cộng hai phần tử trước nhưng khác cơ sở, nên không phải cùng một dãy.

Với $n$ nguyên không âm, $0!=1$ là một cơ sở để tính giai thừa; khi $n\ge1$, dùng $n!=n\times(n-1)!$. Cũng có thể chọn cả $0!=1$ và $1!=1$ làm cơ sở rồi chỉ dùng truy hồi với $n\ge2$. Với $a\ne0$ và $n$ nguyên không âm, cơ sở $a^0=1$ kết hợp truy hồi $a^n=a\times a^{n-1}$ khi $n\ge1$. Các cơ sở này là giá trị biết trực tiếp, không phải lời yêu cầu tiếp tục gọi về số mũ nhỏ hơn.