Counting Fruits, Fibonacci and Obviously Great Functions!

Accessible for all HS grades

Counting Fruits

Let’s start off by looking by considering a smoothie making problem. Suppose we have a selection of fruits, 3 mangoes, 2 peaches and 2 lemons, to choose from to make a smoothie. If we want at least 1 of each fruit in our smoothie, how many ways are there to make the smoothie?

We can symbolically represent all the combinations as

🥭🍑🍋 + 🥭🥭🍑🍋 + 🥭🥭🥭🍑🍋 + 🥭🍑🍑🍋 + 🥭🥭🍑🍑🍋+ 🥭🥭🥭🍑🍑🍋 +🥭🍑🍋🍋 + 🥭🍑🍑🍋🍋 + 🥭🥭🍑🍑🍋🍋 + 🥭🥭🥭🍑🍑🍋🍋 + …

• Note: “+” means “or”. 🥭🍑🍋 + 🥭🥭🍑🍋 means {mango, peach, lemon} OR {mango, mango, peach, lemon}. Writing the symbols next to each other means “and”. 🥭🍑🍋 would mean mango AND peach AND lemon. If we wanted to find how many ways to pick 5 fruit, we would look at all the possibilities which have five fruits, eg: 🥭🥭🥭🍑🍋

We could then write the above expression in terms of exponents.

🥭🍑🍋 + 🥭²🍑🍋 + 🥭³🍑🍋 + 🥭🍑²🍋 + 🥭²🍑²🍋+ 🥭³🍑²🍋 +🥭🍑🍋² + 🥭🍑²🍋² + 🥭²🍑²🍋² + 🥭³🍑²🍋² + …

• The exponents denote the number of fruits. Here, 🥭³ means taking a multiset of three mangoes.

We can simplify the expression above to (🥭+🥭² +🥭³)(🍑+ 🍑²)(🍋+🍋²) However, since we are only considered the number of ways to make a smoothie with some number of fruits, we can simply replace all the fruit symbols with x. Eg: (x+x²+x³)(x+x²)(x+x²). Since we’ve replaced all fruit symbols with x, to find how many ways we can make a smoothie with k fruits, we simply look at the coefficient of xᵏ.

Thus, in the above case, the coefficient of x⁵ is how many ways we can choose 5 fruits from 7 fruits. Therefore, in general, the coefficient of xᵏ is how many ways can choose k fruits from n fruits. This also gives an intuitive argument for understanding the coefficients in the binomial expansion.

Obviously Great Functions

(boringly known as Ordinary Generating Functions)

Now we’re ready to define an Obviously Great Function: An OGF of a sequence a_{n} is a power series where the coefficient of xⁿ is the nth term of the sequence.

• A power series is essentially a polynomial with infinitely many terms. If the polynomial has a finite number of nonzero terms, we can view the other infinitely many terms as 0. (In this case, we will be using formal power series as we are only using xⁿ as placeholders for the coefficients. Thus, we disregard whether the sequence converges or diverges.)

Binet’s Formula

The following is an OGF

What’s so great about OGF’s you may ask. Perhaps manipulating OGF’s allows us to derive a closed-form for the nth Fibonacci number?

The following is the well-know recurrence formula for the nth Fibonacci Term.

For the sake of consistency, we can rewrite this as

Therefore, we can write an OGF for the Fibonacci recurrence relationship. We reindex the summation to start from 2 such that n-2 ≥ 0. Thus, we also have to account for the first two terms of the sum.

Now, we can evaluate each individual sum in terms of A(x)

Thus

Finding the Closed Form

Perhaps decomposing A(x) into two distinct fractions may help us :)

To decompose A(x) into 2 distinct fractions, we first have to find the solutions to quadratic, x²+x-1 = 0. Let -p and -q denote the solutions to the quadratic.

Next, we can find the numerators n and m by comparing coefficients. Since we know that the following equations are true

we can derive

Solving for n and m, we get

Therefore, we can rewrite A(x) as

Now, we want to get both fractions into a similar form such that we can find the sum of the geometric series.

Similarly

Thus, we can rewrite A(x) as

Since the nth term of a sequence is represented by the coefficient of xⁿ in the formal power series.

BABAM!

As you might’ve realised, p and q are the golden ratios!