Skip to main content
Loading Explore guides…
Fibonacci sum pattern · Acedra
Home
Explore
Mathematics
Fibonacci sum pattern
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
52 segments
Copy
Hide video
0:05
Welcome to another Mathologer video. Have a look at this: 1 1 2 3 5 8 ... okay, been there, done that. To death! Obviously that’s the Fibonacci sequence and you know the drill. There, 1+1 is 2, 1+2 is 3, 2+3 is 5, 3 + 5 is 8, and so on. Consecutive terms always add to the next term in the sequence. We’ve all seen this a million times, right? Well, here is something new. Let’s add the Fibonacci numbers. 1, nothing to add so the
0:38
sum is 1. 1+1 is 2. plus 2 is 4. plus 3 is 7, plus 5 is 12. What’s next? Hmm, silly question. Plus 8 is 20, obviously. But that’s not what I am after. Have a look at the Fibonacci numbers and the sums side by side. Can you spot a surprising bonus relationship between the two sequences? No? Well, have a closer look. There are two numbers in the 30s. There are also two numbers in the 20s. And two in the 10s. Can you see it now? I’m sure you can. There, shift the right column
1:14
up by two. 34-1=33, 21-1=20, 13-1=12 and so on. Neat. In other words it appears that the sum up to a certain Fibonacci number is equal to the second next Fibonacci number minus 1. Not hard to prove that this always works. Maybe give it a try yourself as a little challenge and, as usual, leave your thoughts on this in the comments. Anyway, in particular, this implies that the sum up to a certain Fibonacci number is always SMALLER than the second next Fibonacci number. Right?
1:49
The sum up to five is less than the second next Fibonacci number 13. Etch this into your memory because we are going to use it later. Again: The sum up to a certain Fibonacci number is smaller than the second next Fibonacci number. Properly etched ? Cool :) This simple insight will be the key component of a super-ingenious, super pretty and super accessible proof that I plan to inflict on you today. Lots of surprising, fun and very deadly maths to look forward to, promise.
2:25
Okay, apart from Fibonacci, the title of this video also mentions a solitaire army. What army and why are they playing solitaire? Well, the solitaire is not the card solitaire that many of you will be thinking of. No, it’s peg solitaire. Are you familiar with this game? The aim of the standard version of peg solitaire is to jump over and remove pegs, until only one peg remains right at the very center of the board. It’s a tricky puzzle and also an absolute classic. And
2:53
many people don’t realise that peg solitaire is a 17th century viral precursor of the Rubik’s cube.
2:59
Here is a painting of a very proper lady of that era, posing with a French version of the game.
3:06
Anyway, I am sure most of you will have played this game at least a couple times. If you are inspired to have another go at it but don’t own a set, it’s probably easiest to download one of the many peg solitaire apps that come with a number of different boards and fun challenges.
3:21
Here is a quick reminder of how you play the basic game.
3:26
A move in peg solitaire consists of jumping with one peg over an adjacent peg into a hole. And then removing the peg we jumped over. OK, so no real choice for that first move, but what about a second move. There are a few possibilities. There, there, Let’s go for this one. Next move. And so on, until, after a lot of getting stuck and doing this sort of thing you finally solve the puzzle.
3:59
Just as for the Rubik’s cube, there is a lot of really nice mathematics hiding in this game. For example, when you play this game, you’ll usually get stuck with a couple of pegs remaining on the board. Here is an example, of such a dead end. However, if you happen to wind up with just one peg left over, it’s possible to prove that this final peg can only be in one of these five positions. Why is that? If you're interested, Marty and I once wrote about the nice mathematics
4:25
in one of our newspaper columns, which you can read in our nice new book, that one there :) But no need to do that. I’ll also put links to our article and a couple of other nice write-ups in the description of this video. OK, we have Fibonacci and solitaire, and now for the army. To be able to compete with Netflix, let’s up the ante, by turning peg solitaire into a life-and-death game, ... by having leap-frogging soldiers play the role of the pegs.
4:51
Obviously, in this real life version of the game the jumped over soldier will be eliminated. And so will be all the remaining soldiers if the game is not won. So, at most one survivor in the basis game. Delightfully cut-throat, hmm ? :) Maybe also something for the writers of the second season of the squid game to consider. Anyway, here is a little challenge for you. Imagine you are a solitaire general, and suppose you
5:15
really want to save your favourite green soldier. That fellow there. Show that this is impossible, show that the green soldier can never survive. Harder question: Which of these 5 soldiers can possibly win the game and survive and which cannot? Leave your answers in the comments.
5:37
Now for the real challenge. This is the world of solitaire which is just an infinite square grid. This world is divided by the red line into two opposing kingdoms, the TOP and the BOTTOM. The King of the Bottom who is sick of being at the bottom has decided to invade the TOP.
5:53
You are the general of the bottom army and are charged to push as far as possible into the top kingdom, and to sacrifice as few soldiers as possible along the way. To do this you first have to set up your army at the bottom and then make solitaire moves to invade the top. Makes sense? Not really? Well, it’s a war. Did anything ever make sense in war? Anyway, those are the rules of our deadly game of solitaire. Also, if at any point you feel the urge to participate in one
6:22
of the solitaire battle challenges ahead of us, just pause the video, dust off you your checker board or use the custom online app that I’ve linked to in the description of this video. Okay, ready for war ? Well, at least one thing is clear: You cannot invade the top by yourself. You definitely need at least one soldier to leap-frog into the top with a solitaire move. So, no James Bond missions here. Of course, if you want to survive the invasion it is also crucial to
6:51
choose wisely who among the soldiers you want to be. In the case of this simple starting formation you definitely want to be that guy at the bottom. ? Okay, one soldier was sacrificed along the way, but at least it wasn’t you and you managed to advance one step into enemy territory.
7:09
How many soldiers do you need to advance two steps? And how can you figure out a starting formation? Easy. At the end of your mini-campaign you want to be here. Two steps into the TOP. Well, pretty clear where you most likely will be coming from. And, in turn, where did those two guys come from? Well, maybe the bottom one jumped in from the side like this.
7:33
Working backwards one more step, it’s now clear how we can complete our setup.
7:39
Done. This rotated L formation will do the job. And, of course, you want to be the guy on the far right to start with. Once more.
7:48
Easy. What about three steps into enemy territory? Want to give it a go yourself. Yes? No? Anyway, here is an idea: Our rotated L formation got us 2 steps in. So if we can arrange for an intermediate position that is shifted one step up from what we see in front of us then we’ve won.
8:08
Again, it’s not hard to guess a working initial formation by working backwards from this shifted up L formation. Maybe give it a try yourself. Anyway, here is the starting formation that you most likely will end up discovering. Let’s check that this really works. Everybody, Charge !!!
8:28
There we go, the rotated L shifted one up :) Done. And it looks like we might be getting close to being able to conquer the entire top kingdom. Let’s see whether we can see a pattern emerging.
8:43
Okay, to get 1, 2, and 3 steps into the top we used 2, 4 and 8 soldiers. And it’s actually not hard to see that these are the minimal numbers of soldiers needed. The starting formations are mysterious, and definitely no pattern jumps out at me. What about you? But definitely, 2, 4, 8 screams powers of 2 and so it should be 16 soldiers next, right? Wrong :) Surprisingly, it turns out that you need a minimum of 20 soldiers to advance 4 steps into enemy territory.
9:15
Here is one arrangement of soldiers that achieves this feat. Again not TERRIBLY hard to come up with this initial formation by solitairing backwards from the 3 steps solution that’s been shifted up by one. Let’s unleash this army on the enemy and check that it really does the job. There we go.
9:32
Everything is nicely advancing there. Okay. Good. There is the 3 steps configuration that we’ve used before just shifted up one step. Great, all clear clear sailing from here. There,
9:46
there, there, there, there. That’s the 2 steps configuration that we’ve used before just shifted two steps up. And, might as well, this is the 1 step configuration that we’ve used before
9:56
just shifted three steps up.
10:01
Okay, major plot twist just around the corner. At the moment things are pretty confused. There’s no clear pattern in the starting formations, not even in the number of soldiers in these formations. Still, it’s pretty clear how you would go about extending from one starting formation to the next: Just some more backtracking should do the trick, right? Fine. Suppose your life depends on just determining the order of magnitude of the next minimal number of soldiers. What do you say,
10:28
for getting five steps into enemy territory? Will that number be in the tens? Will it be in the hundreds? Or in the thousands? What do you think? Well, pretty sure you won’t be able to guess, unless you’ve heard of this before, in which case you’re not guessing are you? It turns out that it is impossible to get 5 steps in no matter how many soldiers you have at your disposal. Pretty amazing, isn’t it? How’s that for a Whats-next-surprise? :) Alright, what I want
10:54
to do now is show you an ingenious and absolutely beautiful Fibonacci-powered proof for this amazing fact. This proof is due to the Austrian mathematician Martin Aigner. and was published in 1997 in the Mathematics Magazine. Martin Aigner’s proof is a variation and major refinement of a 1961 proof by the great John Conway that uses the golden ratio as its main ingredient.
11:21
Numberphile covered the Conway proof back in 2018 under the title “Conway’s checkers”. Definitely also worth a look and I’ll put the relevant links in the comments. Anyway, now may be a good time to grab a mug of hot chocolate, and get comfy for the main battle: The proof that 5 steps in is not possible. Ready?
11:47
As usual I’ll illustrate the proof using a specific fun example. Let me show you that starting with this menacing looking arrow formation you cannot possibly solitaire your way to the yellow square on the 5th row. To begin, let me introduce you to the triangles of death associated with the yellow square. Here we go. There are infinitely many of these triangles and every one of these triangles is supposed to continue forever at the top.
12:15
Now, eventually these triangles associated with the yellow square will engulf any finite army and any square where this army could possibly move to as we jump around. Here it’s important to note that this formation consists of 12 soldiers and so there will be at most 11 jumps, which puts a limit to how far this formation can move. Let’s suppose this death triangle here does the trick. The
12:42
ACTUAL triangle would have to be a bit larger to make sure that the formation cannot move outside as it evolves. But in order to be able to fit everything on the screen I’ll leave it like this. Doesn't make any difference as far as explaining the proof is concerned. Okay, now fill in the triangle with Fibonacci numbers like this. Whoa :) Sort of Pascally, but it’s definitely not that. Can you see how it’s made? Let’s have a closer look at how the Fibonacci numbers are placed.
13:22
All clear? Okay, now we add up all the numbers in our arrow formation and call the resulting number the weight of the arrow. Of course, as we are jumping around we expect this weight to change. Now the first really nifty thing about our Fibonacci setup is that on every jump the weight will either stay the same or it will decrease. Let’s check this. There, when we jump, the 3 and the 5 get replaced by the 8 and since 3+5 = 8 the weight does not change.
13:51
The same will be true every time we jump up as we just did. That’s easy to see, right? That’s just the Fibonacci rule in action. Going the other way, jumping down will obviously decrease the weight. Right, as in this example, the 5 and the 3 in the weight get replaced by the 2, giving a smaller weight. There Similarly, you can easily check for yourself that jumping towards the vertical symmetry axis of the triangle leaves the weight unchanged. And, jumping across the symmetry
14:19
axis or away from it the weight decreases. Again, summarising it all, overall the weight of a formation will always either stay the same or decrease as it evolves. Now comes the first punchline of the proof. If our arrow formation could evolve to include that 144 at the top, then of course at that stage of its evolution the weight of the formation would be at least 144. Makes sense, right? However, when you actually add the numbers in the initial arrow formation
14:52
to calculate its initial weight, you find that this weight is only 52. But 52 is not greater or equal to 144 and we conclude that starting with the arrow formation we cannot reach the 144. What an ingenious argument, don’t you think?
15:10
Similarly, given any starting formation and any target square on the 5th row, we can use a monster death triangle to prove that the formation cannot reach the target square. And this then proves that 5 steps in is impossible. But how we can possibly show this for all the infinitely many starting formations and target squares? That’s definitely not clear yet. But it will be once I highlight another amazing feature of our Fibonacci labelling. It’s the fact
15:41
that the weight of any starting formation contained in a triangle of death is less than the label of its yellow base square. Wait what? What did that all mean? Well, for example, in this triangle of death the yellow base square has label 144. And, what I am saying is that any formation below the red line contained in the triangle will have weight less than 144. In other words, I am claiming that any starting formation contained in the orange tip will have weight less than 144.
16:09
How do we prove this? Well, the weight of our starting formation is definitely not greater than the weight of the orange tip. So all we need to show is that the weight of the orange tip is less than 144. Of course, in this special case we could just add up the numbers. But let’s do the summing in a way that will work for all possible triangles. The key ingredient is the fact from the
16:34
beginning that I asked you to etch into your mind. Oh no! You forgot it? OK, you’ll have to stay back after the video to clean the blackboards, and here’s a reminder. Repeat after me: the sum up to a certain Fibonacci number is less than the second next Fibonacci number. Got it now? Alright, to find the weight of the yellow tip, let’s sum the numbers column by column. The sum up to 13 as in this column is less than the second next Fibonacci number which is 34. Similarly,
17:03
the sum of this column ... is less than 21. and so on. Okay, so the weight of the tip is less than the weight of the grey bar. Let’s split the bar in two. Aha, can you see where I am going with this? We’ll use the fact that we etched into our minds twice more. We first conclude that the weight of the blue bar is less than the second next Fibonacci number up from 34 which is 89. Second, the weight of the pink bar is less than the second next Fibonacci number up from 21 which is 55.
17:40
And so the weight of our orange triangle tip is less than the sum of the two consecutive Fibonacci numbers 55 and 89. And what’s that sum? Yep, Fibonacci strikes again. Of course the sum of these consecutive Fibonacci numbers is the next Fibonacci number, which is 144. To recap, with the aid of Fibonacci we’ve convinced ourselves that 144 is greater than the weight of the yellow triangle tip, and therefore also greater than the weight of any starting configuration contained in
18:10
that tip. How spectacularly nice was that? Okay, and in the same way you we can show that The weight of any starting formation in this triangle of death is less than 89 Less 55 in this one. less than 34, and so on. And of course the same is true going in the opposite direction looking at larger and larger triangles of death. Okay, so with this property of our triangles of death in hand we can
18:33
really finish the proof. Start with your favourite space invaders inspired formation. and any target on the 5th row. Then there will be a triangle of death based at the yellow target that contains all possible squares that the formation could possibly reach during one of its possible evolutions.
18:55
Then, as we’ve seen, in this triangle of death the weight of the formation is less than the label of the yellow target and consequently the formation cannot reach the target. And therefore, overall, we can be sure that we cannot advance 5 steps into the enemy territory. Tada!! Sooper dooper nice proof, don’t you agree. There are all sorts of variations of this game that people have considered to get to the 5th row and beyond anyway. For example,
19:21
if in addition to jumps in the vertical and horizontal direction we also allow diagonal jumps, advancing 5 steps is possible. Or if you allow for just one position of your starting formation to be occupied by two soldiers, you can also get 5 steps in. Or, filling in all of the bottom kingdom with infinitely many soldiers and allowing infinitely many jumps can also get you five steps in, in a very weird and counterintuitive way. Instead of using a 2d grid you can use a 3d one
19:50
with a plane separating it into two parts. If you do that, 7 is the maximum number of steps you can advance into enemy territory. You can also consider what happens if you play the game in higher dimensions, etc. And most of these scenarios you can analyse using Fibonacci numbers. Very nice and powerful stuff. I’ll include some more links in the comments.
20:10
And that’s all for today. To finish off here is an animation of how a 2d solitaire army can advance beyond level 5 if diagonal moves are allowed. Enjoy:)
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat