Using Reducible Functions in Math Problems

A very entertaining way to solve problems which seems hard otherwise…

A Simple Search…

Let’s have a look at some easygoing questions which you can solve by trying every possible case. But we should find more efficient solutions to those questions. You know what I mean… Rather than counting by fingers, we are going to find a solution which would give the direct answer without any counting. First, let me give an example of that kind of questions.

Suppose you are flipping a coin. You write down the result in every single flipping as heads or tails. Now, let’s say you wanted to make an experiment on this coin and wrote down every possible TH series whose length is three.

So you would have this 8 different series:

TTT, TTH, THT, HTT, THH, HTH, HHT, HHH.

Then you continue with the series of length 4 which means you wrote 16 different series. Now before going any further with the length let’s say you wanted to examine the number of series which does not consist any consecutive T. It is easy to count when you are looking for the series of length 3 but then you did not stop wondering and thought what would be the number of series not containing any consecutive T whose length is 10? Well, I wonder that too. So let’s find out the answer together. First of all, we should not approach the problem in the way we approached when there was only 8 series. The reason is obvious: There would be 2¹⁰ = 1024 possible series to check whether it contains any consecutive T. You can suggest computing with python or any other programming language at this point and yes, that would be a lot easier than the approach I am about to show you. But for now, let’s assume that the only tool we have is paper and a pencil.

Now, it is time for the more beautiful solution…

First, let me start by making the notation clear. From now on let f(n) denote the number of series which does not contain any consecutive T and whose length is n. For example, f(3) = 5, f(2) = 3, f(1) = 2. Let’s make a table to see the relation between n and f(n).

Did you notice something? For every n>3 it seems like f(n) = f(n-1) + f(n-2). This is such a good formula. But as Ali Nesin says and I quote “Finding the formula is for smart people but believing a formula is for dumb people.” so we have to prove that this formula holds.

Now, let’s prove that the formula holds for every integer n, bigger than or equal to 3. In order to do so, we are going to build the formula from scratch without any assumptions.

By the definition of f(n), you are trying to find f(10). Let me put 10 aside for now and focus on a more general solution. Well, now that we sensed the answer above one might think that it is logical to find a relation between f(n) and f(n-1). Something that we can use in order to get through f(n).

The only criteria we want the series to provide is not containing any consecutive Ts. Can you think of anything? I would recommend you to stop for a minute and think of the possible ways of approaching the problem.

Here comes the lifechanging part…

Have a look at the board below ☟

Now let me explained what has happened on the board. First, we approached the problem from the last element of a particular sequence. If the last element is heads (H) then we shall add f(n-1) and add the number of sequences which end with tails (T). If the last element is tails then we know for sure that the second last element of that sequence must be heads (H). Otherwise, there would be two consecutive tails which contradict with the property. Thus we shall add f(n-2) for all the ones which end with T. As a result, we gained brilliant formula which is f(n) = f(n-1) + f(n-2). And we gained this formula simply by counting the number of sequences that end with T and the number of sequences which end with H.

We were looking for f(10). The rest is very easy as we have a formula. You can easily compute f(10) by simply computing f(2) and f(1) because the rest comes from the formula. f(10) = 144.

Indeed, the formula we arrived is a special relation. It is called “Fibonacci Numbers”. I cannot let you go without giving you some historic background for the formula so keep reading…

Historical Background…

Fibonacci series is defined as follows:

F(0) = 0, F(1) = 1 and for every n≥2, F(n) = F(n-1) + F(n-2)

The beginning of the sequence is thus: 0,1,1,2,3,5,8,13,21,34,55,89,144,…

Fibonacci sequence is named after an Italien mathematician Leonardo of Pisa. He announced the sequence to the European world but the first implementation of the sequence goes back earlier India, as early as 400 BS and was first used by Pingala, an Indian poet, to enumerate possible patterns of Sanskrit poetry formed from syllables of two lengths.

Fibonacci numbers appear so much in mathematics so that there is a journal called “Fibonacci Quarterly” dedicated to their study. Fibonacci numbers appear in various aspects such as computer algorithms, branching in trees, the arrangement of leaves on a stem, the fruit sprouts of a pineapple, the flowering of an artichoke, an uncurling fern, and the arrangement of a pine cone’s bracts.

Here are some of the applications of Fibonacci Numbers:

From Wikipedia,

1. The Fibonacci numbers are important in the computational run-time analysis of Euclid’s algorithm to determine the greatest common divisor of two integers: the worst case input for this algorithm is a pair of consecutive Fibonacci numbers.

2. Yuri Matiyasevich was able to show that the Fibonacci numbers can be defined by a Diophantine equation, which led to his solving Hilbert’s tenth problem.

3. The Fibonacci numbers are also an example of a complete sequence. This means that every positive integer can be written as a sum of Fibonacci numbers, where any number is used once at most.

4. Moreover, every positive integer can be written in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. This is known as Zeckendorf’s theorem, and a sum of Fibonacci numbers that satisfies these conditions is called a Zeckendorf representation. The Zeckendorf representation of a number can be used to derive its Fibonacci coding.