# Fibonacci Sequence: Running Sum

This article is in continuation of this one.

R**ecap** In the previous article, I had tried to emphasize how

nᵗʰ Fibonacci Number = Number of ways to climb n step staircase, where you have only two possible options to move, either by climbing 1 step or 2 steps at a time.

In the same article, I have mentioned some other possible representations of the Fibonacci Sequence. One of them is the number of ways to tile a N x 1 board with a 1 x 1 square and 2 x 1 domino. By writing the recurrence relation for the same, we can state that NoOfWaysToTile(n) = nᵗʰ Fibonacci Number.

In this article, I am going to discuss my approach to the Running Sum Identity of the Fibonacci Sequence using the same relation.

**The Running Sum of Fibonacci Sequence**

**The Left Hand Side (L.H.S.)**

The L.H.S. of the equation has 2 parts ** Fib(n)** and

**.**

*(- 1)*Fib(n) = nᵗʰ Fibonacci Number = No of ways to tile n x 1 board.

But what does this

**‘**represent?

*one’*Since everything in this relation is related to ‘

*the*

*number of ways to achieve tiling’*then this

**‘**can only represent a scenario. That scenario can be ‘the occurring some specific event’, say

*one’***E**, and this event E can only occur once. The negation sign before

**‘**is actually excluding the possibility of happening of this event

*one’***E**.

Now L.H.S. = No of ways to tile n x 1 board - Occurring of the Event E.

In other words,

**L.H.S. states the number of ways to tile the board without the occurrence of that special event E.**

**What can E be?**The only thing special about E was that it can happen only once, in any scenario, it means that whatsoever be the size of the board, the E can only and only occur once.

Generally, these kinds of cases are very basic or formally known in Mathematics as

**trivial.**

On the basis of all the facts and assumptions

- E has to have occurred only once.
- E hints to be a trivial case.

Finally, after looking at all the types of patterns, I assumed that E should be a case where we tile the whole board using only squares. I wasn’t sure but yes it worked.

**E = the event when we tile the whole board with squares only.***“Clearly this can occur only once whatsoever be the value of n.And kind of the case was trivial also.” — in support of my assumption.*

**Back to L.H.S.**

Now L.H.S. becomes the total number of ways to tile the board excluding the case where we tile the whole board with 1 x 1 square, without using any domino.

Or, **L.H.S. is the number of ways to tile board with at least one domino being used somewhere.**

This second interpretation actually helped in deducing the other side of the equation

**The Right Hand Side of the Equation (R.H.S.)**

Now, it was clear that if I am able to emphasize that this summation says the same story as the latter meaning of L.H.S., then the job is done.

L.H.S. says that

“ I am the number of ways to tile board with at least one domino being used somewhere.”

Let us take some close observation on the summation

- Each term in the summation is a positive term, hence no exclusion is happening in this part of the equation
- Since there is no term with a minus sign, then each of the terms in the expression is a representation of a case, and all the cases are mutually exclusive (i.e. no two cases overlap)
- And the summation of all the terms gives the total number of ways to perform the act, this means that the cases are exhaustive(i.e. covers all possibilities)

**The First term: Fib(n - 2)**

Fib(n - 2) represents the number of ways to tile (n - 2) longboard.

Since we have 2 tiles of the board empty and Fib(n - 2) solely doesn’t guarantee that a domino will come at least while tiling the whole n x 1 board, we can put the domino at the very beginning.

The First Term = Number of ways to cover the whole board with the first domino placed at the first-second tile = 1 * Fib(n - 2) = Fib(n - 2)

**The Second Term: Fib(n-3)**

Taking inspiration from the first term we can say that in the second term should count the cases when the first domino is placed at the second-third tile. So the first tile should obviously be tiled with a square.

The Second Term = Number of ways to cover the whole board with the first domino placed at the second-third tile

or The Second Term = (Number of ways to tile the 1 x 1 board with only squares) * (Number of ways to place domino at second-third tile) * (Number of ways to tile rest of the board, the board of length n - 3)

**The Third Term: Fib(n-4)**Following the induction

The Third Term = Number of ways to cover the whole board with the first domino placed at the third-fourth tile

or The Third Term = (Number of ways to tile the 2 x 1 board with only squares) * (Number of ways to place domino at third-fourth tile) * (Number of ways to tile rest of the board, the board of length n - 4)

**The Kᵗʰ Term: Fib(n - (k + 1))**The Kᵗʰ Term = Number of ways to cover the whole board with the first domino placed at the kᵗʰ — (k+1)ᵗʰ tile

or The Third Term = (Number of ways to tile the (k - 1) x 1 board with only squares) * (Number of ways to place domino at kᵗʰ - (k+1)ᵗʰ tile) * (Number of ways to tile rest of the board, the board of length n - k - 1)

Hence each of the terms in the summation represents a case when the first domino is placed at a specific position. These cases adhere to the rules of being mutually exclusive and forming an exhaustive set.

Hence we can say that **R.H.S. also represents all the ways to tile the board at least using a domino.**

Finally, it’s done.

Hence we can say **the Running Sum of the Fibonacci Sequence equates the number of ways to tile the n x 1 board with using at least one domino, using two different methods of counting, known as the inclusion-exclusion principle and exhaustive counting.**

Next time you encounter a problem that requires you to add the terms of the Fibonacci Sequence just remember the story, you will not need to remember the formula. And I think that if we change the dimensions of the tiles being used here, still we can derive a relation of this kind, with newer tiles or for a sequence somewhat similar to the Fibonacci Sequence.

**Towards the End…**The article is verbose and overexplained at a lot of places. But I had to put down what all things came to my mind while looking at the equation and finding out what it actually emphasizes. I thought if I’ll put up the solution directly then most of the things will seem magical and most of you will believe that I just crawled on the net for two days and copy-pasted it here.

Yes, I haven’t used the climbing stairs interpretation because I wasn’t comfortable with it in the beginning. Later, I thought it would be easier to put things the way they occurred to me rather than translating to some other problem, that too with no help in explanation.

I had seen my teachers explaining to us some complex mathematical formulas of combinatorics (

*nCr*,

*nPr*) using interpretations like these. They used to build a thought around the basic series first, this would generate a world (imagination) with rules. Then, they would try to explain what a formula, proven identity, or statement of a related theorem of the sequence will actually represent in that world and is actually valid using simple mathematical tools like set theory and basic counting. Here I have tried the same.

*Dedicated to Dr. Saurabh Priyadarshi, Mr. Anshul Singhal and Mr. Anshul Tomar*

And after a very long ending note,*Ram Navmi ki Shubhkamnayen*

Bye :)