New: 201 pattern programs with tested code in C, C++, Java and Python Explore patterns

Fibonacci Triangle

Read summary with AI tools

The Fibonacci triangle lays the Fibonacci series out in rows: one number on the first row, two on the second, and so on. The series never restarts, so five rows use the first fifteen terms and the last row ends at 610.

Quick answer: Keep two running values, a = 0 and b = 1. Row i prints i numbers. Each time, print b and then step the series forward with next = a + b; a = b; b = next. Because a and b are never reset, every row carries on from where the last one stopped.

This program is part of the Series Patterns collection.

Table of contents8 sections
  1. Output
  2. How the fibonacci triangle works
  3. Program in C
  4. Program in C++
  5. Program in Java
  6. Program in Python
  7. Time and space complexity
  8. Frequently asked questions

Fibonacci Triangle output

Output (n = 5):

   1
   1   2
   3   5   8
  13  21  34  55
  89 144 233 377 610
Fibonacci Triangle layout diagram, row by row (n = 5)
The numbers of the fibonacci triangle laid out row by row (n = 5).

How the fibonacci triangle works

The shape is a plain right triangle, row i holds i numbers. The values are the interesting part. Instead of working each one out from i and j, the program carries two numbers through the whole triangle: b is the term to print and a is the term before it. Their sum is always the next term, so one addition per number is enough.

  1. Set a = 0 and b = 1 before the loops start.
  2. Run the outer loop for i from 1 to n, one row per pass.
  3. Repeat i times: print b four characters wide, then set next = a + b, a = b and b = next.
  4. Move to the next line.

Key takeaways

  • The shape is an ordinary right triangle; only the values come from the Fibonacci series.
  • a and b sit outside both loops, which is what lets the series run on from row to row.
  • Printing every number four characters wide keeps the columns straight up to 9999.
  • Five rows print 15 terms. In general n rows print n(n + 1) / 2 terms.

Fibonacci Triangle in C

#include <stdio.h>

int main(void) {
    int n = 5;
    int a = 0, b = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            printf("%4d", b);
            int next = a + b;
            a = b;
            b = next;
        }
        printf("\n");
    }
    return 0;
}

Fibonacci Triangle in C++

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n = 5;
    int a = 0, b = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cout << setw(4) << b;
            int next = a + b;
            a = b;
            b = next;
        }
        cout << endl;
    }
    return 0;
}

Fibonacci Triangle in Java

public class FibonacciTriangle {
    public static void main(String[] args) {
        int n = 5;
        int a = 0, b = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                System.out.printf("%4d", b);
                int next = a + b;
                a = b;
                b = next;
            }
            System.out.println();
        }
    }
}

Fibonacci Triangle in Python

n = 5
a, b = 0, 1

for i in range(1, n + 1):
    for j in range(i):
        print(f"{b:4d}", end="")
        a, b = b, a + b
    print()

Time and space complexity

Each of the n(n + 1) / 2 terms costs one addition, so the program runs in O(n²) time. It only keeps a, b and the loop counters, so the extra memory is O(1).

Frequently asked questions

How do I start every row again at 1?

Move a = 0 and b = 1 inside the outer loop, just above the inner loop. Each row then prints the first i terms on its own: 1, then 1 1, then 1 1 2, then 1 1 2 3.

How many rows fit before the numbers overflow?

A 32-bit int holds Fibonacci numbers up to the 46th term, 1,836,311,903. Nine rows use 45 terms, so nine rows is the limit with int. With long long in C and C++, or long in Java, you can go to 13 rows. Python integers never overflow.

How is this different from Pascal’s triangle?

In Pascal’s triangle each number is the sum of the two numbers above it, so every row starts and ends with 1. Here the rows have no link to each other; they are just one long series cut into pieces. The two are related, though: the shallow diagonals of Pascal’s triangle add up to the Fibonacci numbers.

Why does the series start with a = 0 and not a = 1?

With a = 0 and b = 1 the first two printed terms are 1 and 1, which is the usual start of the series. Starting with a = 1 would skip the second 1 and print 1, 2, 3, 5 instead.

Authored by

Ghanendra Yadav runs Pattern Programs from Bangalore, India. The site started in 2020 to help students practise loops and logic through pattern programs in C, C++, Java and Python. Every program published here is compiled and run before it goes live, and the output shown is the real output.

Latest articles

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.