A Fascinating Frog Problem - Numberphile

[@Angzt]

If you allow jumps of length 1, 2, or 3, you end up with the (fittingly named) Tribonacci numbers where each number is the sum of the three previous numbers: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149.

[@adityakhanna113]

In the limit you get compositions, which are all th ways to break a number. The metallic ratio of compositions is 2, which is what you notice for n-bacci

[@SanneBerkhuizen]

I'm glad there is a name for the thing I expected to exist.

[@OBGynKenobi]

I knew tribbing somehow had to be part of this.

[@idontwantahandlethough]

@@adityakhanna113 n-bacci sounds like a pasta you make with chemistry

[@IceMetalPunk]

And if you allow either jumps to women or jumps to sandwiches, you end up with the Tribbiani numbers.

[@Greenthum6]

Interestingly, if you replace the frog with a grasshopper, the answer will be identical regardless of the color of the grasshopper.

[@gianlucazinarof8617]

Spittin facts

[@Alittlebitofeverythingoffical]

😎😎😎

[@RFC3514]

Amphibionacci? 🐸

[@numberphile]

Bravo

[@j.vonhogen9650]

That's really clever! 😅

[@Becky_Cooling]

*round of applause*

[@Ajay-m4g]

we can also do it with combinatorics but then after it we have to add 100C0 +99C1+98C2+........+50C50

[@Godsbane]

Ribbitnacci.

[@thorjelly]

Dude is rocking pi, chains, math equations, and two pokeballs on his arms. What a baller.

[@TomRocksMaths]

[@dfunited1]

​@TomRocksMaths I'm sure there's a story behind the 3 on your left ring finger, but I don't want to start an argument about thumbs.

[@JohnPlechaty]

I believe he has the navier-stokes equations about fluid dynamics tattoed

[@rafael.antonioli]

And is that the Axii sign from the Witcher too?

[@markkrutzmann6862]

​@@dfunited1 Isn't that an e for Euler's number? I, an engineer, don't see the difference between e, pi or 3, so in a sense we're both right.

[@yessopie]

People heard about "exponential" during the pandemic, but I think very few people learned what it actually means... most people still think that "exponential" is just hyperbole for "a lot".

[@jamesknapp64]

I've seen too many growth graphs and people say "thats exponetional growth!" and I'm stating "thats quadratic, not even close to exp".

[@TIO540S1]

Yes, and it makes me cringe.

[@kwanarchive]

All those people are the ones who say "but when will I need this in real life?" during maths class. They're also the people who buy houses they can't afford.

[@EvincarOfAutumn]

“Exponential* growth!” * logistic, but like, the fast part

[@EebstertheGreat]

@@EvincarOfAutumn Maybe it was true exponential growth, and there are now quadrillions of COVID cases. They just don't want you to know that the MIB spread it around the galaxy.

[@GeorgeCilley]

I like to believe that Tom lives in that chair, and Brady just visits him from time to time.

[@TomRocksMaths]

can confirm.

[@AgentM124]

Why are the books in little cages. Does this library not have free range books?

[@trimeta]

The cages are there for your protection.

[@_nemo171]

The cages are another layer of protection to frog plages.

[@murk1e]

Serious answer. It’s a chained library. Back in the day, books were incredibly pricey items - it’s theft prevention.

[@DurinSBane-zh9hj]

@@murk1e Nowadays the theft happens when you buy textbooks at the start of the year

[@BobJones-rs1sd]

@@murk1e Chained libraries have actual chains. That is, the books are literally connected to the shelves with chains and rods. This isn't a "chained library." These are just standard book cages used in rare book rooms. And there's no "back in the day." You can see the display case in the back, likely containing exhibits. Assuming this is a reading room in a rare books area at Oxford (where Tom works) there are likely individual books in those cages worth thousands of pounds, even tens of thousands of pounds each. In this case it's not just theft prevention, but likely preventing access to those who may want to randomly browse old and fragile books without permission. It's very common in such areas in libraries also to be required to stow all your personal items in lockers and undergo extensive bag checks to ensure you're not smuggling out leaves torn out of manuscripts or something (which alone can sometimes be worth thousands of pounds, depending on the source). Depending on the level of security, even allowing the markers and classic Numberphile "brown paper" into the room could require special permission.

[@528Circle]

I love these videos. A gentle reminder to myself of just how much there is to learn, and how little I actually know.

[@davidstigant9466]

The frog/lily pad problem leads to a lovely formula for calculating the nth fibonacci number in log(n) time rather than n time. Rather than thinking about the number of trips by landing on the pads near the end, think about landing on the pads in the middle. If n is even, then every path must land on the middle pad or the one before that and the one after it. There are x(n/2) ways to get to the middle pad and x(n/2) ways to get from the middle pad to the nth pad so there are (x(n/2))^2 ways to get to the end landing on the middle pad. If you don't land on the middle pad, you must land on the one before it and the one after it. There are x(n/2-1) ways to land on the pad before the middle, 1 way to get from 1 BM to 1AM and x(n/2-1) ways to get from 1AM to the end. So there are (x(n/2-1))^2 ways to not land on the middle pad. And thus, x(n) = (x(n/2))^2 + (x(n/2-1))^2 ways to get to the end. For example, x(8) = x(4)^2 + x(3)^2 = 5^2 + 3^2 = 34 If n is odd, you can similarly show that x(n) = x((n-1)/2)*x((n+1)/2)+x((n-3)/2)*x((n-1)/2 and using the fact that x((n+1)/2) = x((n-1)/2 + x((n-3)/2), you end up with x(n) = x((n-1)/2)^2 + 2x((n-3)/2)*x((n-1)/2. For example, x(7) = x(3)^2 + 2x(3)x(2) = 3^2 + 2(3)(2) = 21 Then, if you want to, say, evaluate x(100), you need to evaluate x(50) and x(49), which require you to evaluate x(25), x(24) and x(23) (although, you can reduce that to just x(24) and x(23)) which require you to evaluate x(10) and x(11) etc. It takes a total of ~log2(100) steps.

[@matejlieskovsky9625]

That is a neat intuition for the use of fast matrix exponentiation!

[@Anonymous-df8it]

Leaving a reply to remind me of this comment :)

[@JMurph2015]

Same dropping a comment to work this out on paper sometime 👍🏻

[@SimonClarkstone]

Yours speed-up is counteracted by how the size of the result grows linearly with the input. Unless you assume that all multiplicatrons take the same time regardless of the number of digits involved.

[@matejlieskovsky9625]

@@SimonClarkstone assuming we're looking for the n-th fibonacci number, we'll get a Theta(n)-bit number. Additions: We'll need Theta(n) additions of which half work with numbers at least half the length of the result. Assuming addition runs in linear time, we get Theta(n^2) runtime. Matrix exponentiation: We'll need Theta(log n) multiplications (matrix size is O(1)). However, the size of the numbers changes rapidly, making the vast majority of time be spent in the last iteration. In the end, the question is how well you can multiply, but with modern tools, fast matrix exponentiation should be faster for large values of n.

[@Phanatomicool]

I remember there being a leetcode problem about climbing stairs that was analogous to this problem. My solution was an equivalent form of the sum of binomial coefficients, but then i saw other peoples solutions being fibonacci sequence and was so confused lol.

[@NabeelFarooqui]

I've seen that. I understand the video but i don't know how they were solving it

[@stickfiftyfive]

The sums of the diagonals of Pascal's triangle (binomial coefficients) are the Fibonacci numbers.

[@akirakato1293]

If you’ve done dynamic programming you’d have the intuition to figure out the condition that constructs that recurrence relationship then from there it’s obvious.

[@lukevideckis2260]

You solution is related to how if sum of the slants of pascals triangle, you get the Fibonacci numbers: summing up the slants in pascals triangle gives exactly the same binomial coefficients as in your solution

[@MrLongCrash]

I didn't check the solution, but just printed output of brute force solution. Thankfully, Fibonacci is quite recognizable.

[@germaindesloges5862]

This problem is actually the way the fibonacci numbers were first discovered in India, way before it was discovered in Europe. Instead of lilipads ans leaps, musicians were interested in the number of songs of a given length made with short (1) and long (2) beats.

[@sherlockshlome473]

Indians use morse code for their rhythm bwahahaha 🤣

[@AmmoGus1]

Are you indian?

[@TheViolaBuddy]

Numberphile actually did a video specifically on the Indian rhythm origin of Fibonacci numbers a little while ago! I knew we were going to get Fibonacci numbers as soon as the setup to this video was described because of the similarity to that video. That previous video is called "The Truth About Fibs," from October 26, 2022

[@250minecraft]

And then they woke up and shat themselves

[@ricepaperpencil1195]

Yeah, that’s why some mathematicians call them the Virihanka-Fibonacci numbers, after the person who discovered the pattern in length 1 and 2 beats

[@georgecataloni4720]

This is so unrealistic. A frog that thinks about how many ways it can jump definitely doesn't have a mate waiting for him.

[@aofthefielde1305]

😂

[@j.vonhogen9650]

12:40 - For some reason, that little frog sound at the end of the long answer cracked me up. 😅

[@asheep7797]

0:03 'An illustration of a frog that's not that bad' merch out NOW!

[@TimMaddux]

He gave his drawing a go, so it’s likely a Parker Frog.

[@sheronmusic]

What a great video! At 6:42 that reminded me of moving up the fretboard of a musical instrument using half steps and whole steps, so I wrote a function to explore that connection and found some pretty interesting stuff: The function: getScales(Total number (of lilypads), Largest Leap Value, Show total # OR Show all solutions spelled out, Keep all duplicates that are the same under rotation or not) I did some exploring of the different cases: getScales(5, 2, 1, 1) shows that example at 6:42 getScales(4, 2, 1, 1) is the example shown at 5:50, but it prints them out in order of smallest hops to largest: [ '1111', '112', '121', '211', '22' ]. If we imagine that the lily pads are not in a line, but rather in a loop, then we can say that 112, 121, and 211 are really all the same family, just rotated around the loop. So for example getScales(4, 2, 1, 0) prints out: [ '1111', '112', '22' ] If you set the maximum leap size to be 2, then the total number of paths the frog can take will be a fibonacci number. If you also remove all the duplicates via rotation, the sequence for the first 12 lilypads (starting from 0) would be: 1, 1, 2, 2, 3, 3, 5, 5, 8, 10, 15, 19, 31 That 31 represents the unique number of musical families of scales that can be made with leaps of either a half step or a whole step. Here's a spreadsheet of them: docs.google.com/spreadsheets/d/1bvIbCPeJdHo92JZThONwRGaIlNGY2LPoCF-2dFC4pe0/edit?usp=sharing If you don't limit the leap value to 2, but set it as the total number of lilypads, and don't remove for duplicates via rotation. EG getScales(6, 6, 0, 1) reads 32 getScales(12, 12, 0, 1) reads 2048 The total number of paths for any number of lilypads will always be a power of two. Here's the sequence for getScales(n, n, 0, 0) for the first 12 n: 1, 1, 2, 3, 5, 7, 13, 19, 35, 59, 107, 187, 351 Where that 351 represents the total number of unique musical families of notes. I made a video about that: kzbin.info/www/bejne/pmKndZSnrqyniKs If you want to play with getScales() here it is: let scales = []; // Helper function to check if two scales are cyclic duplicates function areCyclicDuplicates(scale1, scale2) { // If lengths are different, they can't be cyclic duplicates if (scale1.length !== scale2.length) return false; // Concatenate scale1 to itself and check if scale2 is a substring return (scale1 + scale1).includes(scale2); } // Function to generate scales recursively function generateScales(currentScale, totalNotes, largestStep, currentNotes) { if (currentNotes === totalNotes) { scales.push(currentScale); return; } for (let step = 1; step

[@leoneldelamojr.1810]

Oh the powers of two when not limiting the stepscan be thought of akin to finding the power set of a set. From set theory. Cool find!

[@fariesz6786]

Frogonacci numbers

[@IceMetalPunk]

Ribbitnacci was right there.

[@_nemo171]

🐸

[@jasonjenkins6373]

We get to the best pun after hopping around for just a ribbit.

[@innamordo]

Amphibonacci

[@oldoddjobs]

No

[@arneperschel]

Let's think of a real-world example of an animal that doesn't want to touch water... frog it is! 😂

[@omri9325]

But it's traveling faster by jumps

[@SteveBlais5791]

It should've been cats, lol.

[@RavenMobile]

Cats and bathtubs.

[@albertosierraalta3223]

This video is great but I'm a little dissatisfied about the argument on why the solution must be exponential. Tom draws a tiny curve and says this is exponential, how do you know this is the case and not some crazy polynomial just from the graph? I'm not saying is wrong, obviously this is the answer but it could maybe be argued better, like the fact that that the nth term of the sequence depends on the previous terms which is a feature of exponential growth. In any case, pretty nice video as always

[@kavetovaify]

Yes. Exactly my feelings too. I mean it was obvious that it was Fibonacci sequence but very far from obvious it should be exponential. Particularly after first 4 points. "Oh that looks exponential!". What kind of argument is that?? 😅

[@RunstarHomer]

Yes. That was informal, and actually, not even true. The sequence cannot truly be exponential since three of the terms are colinear. An exponential function and a linear function never intersect at three points. It is only *approximately* exponential (it's asymptotically equivalent to a particular exponential function). As we saw in the final formula, it is actually the sum of two exponential functions. However, it's reasonable that you might notice the shape and think "what if this behaves like an exponential in the limit", and go down a line of reasoning similar to this.

[@WK-5775]

​@@kavetovaifyThe argument is that the increase equals the value of the sequence itself. And, as one sees, it's not strictly exponential, but it's the sum of two exponentials (aka geometric series).

[@bluerendar2194]

To put the argument more clearly: The proof that it is exponential is that the exponential model works. The intuition leading to that proof is 'oh, it looks exponential, let's try that and see if it works' You'd be surprised that this is how a lot of mathematics is first done. A lot of presentation also only give the proof without (or, without adequate) explanation of the intuition or logic leading to the proof. Sometimes, there's follow-up investigations that uncover more meaningful connections, etc. but that's not always guaranteed to have been done.

[@andrewharrison8436]

If you say that the nth term is twice the average of the previous 2 (or in hand wavy terms twice the term that is 1 and a bit earlier) it becomes easier to justify the exponential statement. ... or you could say between twice the (n-2)th term and twice the (n-1)th term. So between 2 to the n/2 and 2 to the n.

[@izme1000]

My approach was to start with 100 jumps of one, and gradually replaces 2 jumps with a single 2-jump. It's fairly easy to work out the permutations of the replaced jump. Work all the way up to 50 2-jumps, and add them together. I haven't done the actual working out, but the logic feels sound.

[@viktorwalheim6827]

In R you can solve it this way: # Number of double jumps a

[@TomRocksMaths]

Anyone worked out the sequence for when the frog can jump 1, 2 or 3 spaces?

[@timseguine2]

The Tribonacci sequence of course

[@irrelevant_noob]

Angzt had posted their comment a day before you asked. :-) Quote: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149[, ...] Also, 14:55.

[@TomSinister03110]

Matt Parker did a frog problem a few years ago where the frogs could jump as far as they wanted, and asked about the everage number of hops to the end for n lillypads. I don't remember my solution, but it was great fun to solve.

[@waart778]

Indeed it's still my favourite math question

[@0xero7]

CS majors having leetcode flashbacks rn

[@Rubrickety]

I love the tattoo of one of the most important constants in mathematics on Tom's finger: the number 3.

[@AnirbanBanerjee-xm8cr]

This combinatorics problem is just awesome!

[@IulianYT]

12:00 - nah, I figured it at the very beginning, when got to x_3, and understood that it is the sum of previous 2, because there are only 2 ways to make last jump. And it clicked immediately that this are Fibonacci numbers.

[@VictorAFaria]

Same

[@lvlinty]

I get that Xsub0 (the starting case with no lily pads) makes the math clean at 1... But counting "no action" as an option in the word problem means there are Infinity ways to reach the 100th lily pad

[@polyaddict]

2:11 I love the showcase of the Parker frog

[@johnchessant3012]

11:05 I love the frog blithely hopping across the Fibonacci numbers

[@JoeBorrello]

Wow, that was a very ribbiting video, I couldn’t take my eyes off it.

[@alveolate]

i nearly croaked by the end of it

[@toolebukk]

I, for one, feel like they have toad me all of this before 🤷‍♂️

[@endrankluvsda4loko172]

I was wondering why the frog doesn't just pole volt over to the other side, but then I realized the stick it has is just a tad pole.

[@pglink]

Your pun has spawned many imitators. Kermit me to add my own.

[@some_random_loser]

wait. there's a way to get the nth Fibonacci number _without_ using recursion or loops??

[@250minecraft]

Wait til you learn that easiest way to get nth Fibonacci number is matrix multiplication

[@pierrecurie]

@@250minecraft You can get it even faster with fast matrix power; basically it involves squaring the matrix repeatedly. At that point, the real bottleneck is dealing with huge numbers.

[@250minecraft]

@@pierrecurie I know

[@Access1296]

So, I actually tried to solve this before listening to the whole video, and did come up with a solution. My solution only works for even Fibonacci numbers, but I was still proud of it! You can find the Nth Fibonacci number Fn with the following formula, which is a sum: Fn = sum(0->N/2) of (N-X) nCr X So for instance, the 8th Fibonacci number is… F8 = 8 nCr 0 + 7 nCr 1 + 6 nCr 2 + 5 nCr 3 + 4 nCr 4 = 1 + 7 + 15 + 10 + 1 = 34 (I didn’t know at the time that I was calculating Fibonacci numbers, but it worked out) I reasoned that with an even number of lily pads, you could take 0 double jumps all the way up to N/2 double jumps. If you take 0 double jumps, you have chosen to double jump 0 times across N pads (8 nCr 0). If you perform exactly 1 double jump, you reduce the total number of jumps by 1, and can choose any of those jumps as your 1 double jump (7 nCr 1). If you double jump twice, you again reduce the number of jumps by 1, but now choose two jumps to be your double jumps (6 nCr 2). You continue this process of reducing the number of jumps by one and choosing one extra time until you are only performing double jumps (4 nCr 4). It doesn’t quite work with odd numbers since it requires the number N/2 to be a whole number. Still, it works!

[@ChrisSeltzer]

This is similar to my favorite programming question: The rules are slightly different. The frog's speed always starts at 1 but with each subsequent jump they can increase their speed by 1, decrease their speed by 1, or keep their speed constant. Write a function that takes in an array of booleans representing whether or not there is a Lilly pad at that particular position that returns the fewest number of jumps the frog can cross the river in. Return -1 if it's not possible.

[@thisguyispeculiar]

Average CSc student: "Hey, I have seen this one, this is a classic!" Numberphile: "What do you mean you've seen it? It's brand new!"

[@Half_theBattle]

Cue frog eating a McFly

[@BridgeBum]

​@@Half_theBattleI'm lovin' it.

[@igorbartoshuk9762]

The most decorated mathematician I ever saw. Respect.

[@vlc-cosplayer]

When he started enumerating the simple cases by hand, I had this half-intuition that if you know the number of ways you can travel across N steps, then since those steps will always stay the same even in the case of N + 1, N + 2, etc, it should be relatively easy to calculate how many new steps adding a new tile would give: you don't need to start from scratch every time and brute-force all combinations for all tiles, you can just reuse the previous results (programmers would call this "memoization"). If I'd thought about it a little bit longer, I probably would've made the connection with recursion and thus the Fibonacci series. Too bad my brain is as smooth as a Bernini sculpture. 😔

[@amaarquadri]

If you also solve this problem in a combinatorial way, you can get a different formula for the nth Fibonacci number as a sum of binomial coefficients. x_n = F_(n+1)=sum (n-k choose k) from k=0 to k=floor(n/2).

[@Tscharlieh]

4:27 There I got lost. Why X98+X99 = X100? Wouldn’t it be X98+1+X99+1= X100?

[@NazmulHossainPotato_PeeZy]

My question exactly....

[@prosamis]

Yeah this immediately confused me. In my head my immediate concern is double counting and similar issues

[@thomasd8694]

It’s not about the numbers of jumps, but about the numbers of possibilities. There are no more possibilities to get from X99 to X100 than going for the one jump.

[@Tscharlieh]

@@thomasd8694 But „the one jump“ is exactly what I am missing in the further calculations…

[@vatsalgondrala5402]

(X)n is number of possibilities, not number of steps. In case (X)99 there’s no other options for you. In case of (X)98 we chose the condition that it will jump 2 steps ahead and no other routes are possible.

[@DaKeypunchAr]

14 year old me solving this problem for a freaking leetcode problem when I'm bored by my own project and tired of staring a c++ error is fascinating.

[@Bodyknock]

A fun follow up exercise here would be to solve the recursive function using a Generating Function. The nice thing about that method is you don’t have to guess that the function has exponential growth, the formula at the end eventually just falls out naturally.

[@StoicTheGeek]

This problem was given to my daughter in her early high school maths class. I found it really fun and worked out that it was Fibonacci-related.

[@stickmandaninacan]

1:30 before watching further, I want to make a guess, it feels like it could be something to do with binary representation, so I will guess there are somewhere around 2^50 different permutations.

[@Axacqk]

The "high school" intuition is that when a problem leads to a quadratic equation and the solution is somehow sign constrained, then one root leads to a valid solution and the other is discarded. The idea that the actual solution should be obtained as a linear combination of both roots comes out of the blue.

[@veessee]

Do you know why it is that the solution is a linear combination? My thought was the same, that it would be the nonnegative solution of the quadratic solution.

[@Axacqk]

​@@veessee I don't know how much you know about linear algebra, so I will answer as if you knew only the absoute basics - vectors and matrices. The math the author is hiding from us is probably a couple weeks' worth of Linear Algebra 101. Just to signal what's involved - if you represent the two initial values in the Fib sequence as the column vector vector [1,1], then iterating the recursion that defines the sequence can be reframed as repeatedly transforming this vector with the matrix [[0,1],[1,1]]. After each step, you will get a vector whose coordinates are two consecutive terms of the Fibonacci sequence. On the other hand, every such transformation/multiplication of a vector by a matrix can be understood as a transformation of the whole plane if you consider how it affects any possible vector [x,y] rather than just [1,1]. When viewed like this, this transformation is geometrically equivalent to simultaneously stretching or compressing the plane along two lines through the origin. This might be difficult to visualise, so let me break it down: - there are two lines through the origin, U and V, that are uniquely derived from the matrix - each of these lines has an associated scaling factor, also derived from the matrix - to "apply the matrix" to point P on the plane, you first take the "coordinates" of that point as if U and V were the axes of the coordinate system; that is, you measure the side lengths of the parallelogram with opposite corners at the origin and P, and sides parallel to U and V - then you apply the associated scaling factors to these coordinates; this gives you the position of the point (still in uv coordinates) after the transformation Now if you iterate this procedure, and look at how the u and v coordinates (measured along the lines U and V as described above) change, you will notice that at each step the u coordinate is multiplied by one scaling factor, and the v coordinate is multiplied by the other scaling factor. This means that the sequences of successive u and v values are two independent geometric sequences. So if the uv coordinates of the initial vector [1,1] are called [u₁, v₁], and the scaling factors are called λᵤ and λᵥ, then after n iterations it's [u₁λᵤⁿ, v₁λᵥⁿ]. You recognize the powers of λ from the video, right? Now, we are interested in the xy coordinates, not in the uv coordinates, so we need to map these uv coordinates back to xy; we are also only really interested in the y coordinate, because the Fibonacci sequence is a sequence of numbers, not points. This is where the linear combination comes into play: when you derive this inverse mapping and take just the y coordinate, what emerges is the linear combination of the scaling factors (named λ₁ and λ₂ in the video) raised to the n-th power. I know I am still skipping over details here, but at least you can take my word that this linear combination emerges as a result of a step-by-step derivation, rather than as a divine revelation that "the solution must be of this particular form". Some actual terminology used in linear algebra: - the directions of the lines U and V are represented as vectors called the *eigenvectors* of the matrix - the scaling factors associated with the eigenvectors are called the *eigenvalues* of the matrix - the polynomial that was set to 0 and solved in the video as the equation to get the eigenvalues is called the *characteristic polynomial* of the matrix

[@Mikey_AK_12]

The moment he wrote "x_n = " I realized it was induction, so I paused the video to figure it out. Once I found the formula x_n = x_{n-1} + x_{n-2} I knew it was the Fibonacci numbers. After that I just put "101st Fibonacci number" into WolframAlpha and got the answer, but actually solving the recurrence relation with initial values and getting the exponential formula was better! Great video!

[@TomislavMor]

I haven't watched Numberphile in a while now, it has been a couple of years. My first thought after starting the video was "What happened to James Grime??" 🤣

[@wentbackward]

This is one of my most favourite numberphile videos.

[@jakejarvis6683]

I don't want to come across as insensitive here, but when I was younger my parents encouraged me heavily to pursue academics and steer clear of people piercings and tattoos. It's always refreshing when I see Tom in one of these videos because I did pursue a doctorate and I'm also covered in tattoos. I love the reality we currently live in is not the reality I was told it would be. "You won't get a job if you get tattoos! People will judge you, nobody will take you seriously!" Now we live in a world ran by the people that were told that and rejected it. It's lovely.

[@000aleph]

Same story here. My parents told me "You won't get a job if you're not qualified".

[@Saryk360]

4:45 I don't get why x98 + x99 = x100... I feel like it should be x98 + x99 + 1 = x100, because you still need that last hop ?

[@eruvae1210]

It's not the formula for the number of hops, it's for the number of ways to get there. And that's just (number of ways to get to the previous pad) + (number of ways to get to the one before that).

[@ddturnerphd]

"Just to satisfy my curiousity." is a nice summation of the number of ways that there are to enjoy mathematics.

[@bigpopakap]

Meta has practice interview questions for software engineers, and one of them is basically exactly this, right down to the amphibious set dressing

[@timseguine2]

In coding questions there is an alternate version of the exact same problem about walking up a flight of stairs by ones and twos.

[@1curiocat]

The pond-lily-pad-hopping problem is also isomorphic to the more dry-land-table-top problem of how many ways can you place dominoes on a 2xn rectangle. (It gets a little more complicated, I mean interesting, to count domino placements on a 3xn rectangle.)

[@tomushy]

The frog is so cute, I love its happy smile and eyes!

[@WhyCatsCantFly]

I remember doing this exact problem in high school precalc! I ended up writing code to brute force it, but then proved the pattern on the whiteboard, which was such an awesome realization

[@BugBestieLily]

the frog should definitely do the one block vertical jump for the steak

[@sca4723]

Man, seems molecular dynamics are turning more mainstream and I really like it

[@cndbrn7975]

it get's more exciting when you start exploring primes .. well done!

[@bsharpmajorscale]

I absolutely LOVE linear recurrence relations. After discrete maths in uni, I'd do them for fun. I recently reminded myself how again. The equations where the weird roots or trig functions cancel out are the coolest. The notation here is different from what I learned, but not too dissimilar. We had car for "constant" and "ratio," I think.

[@joebloggs3551]

I really love that room.

[@ErikLeppen]

I love how you actually derived a direct formula for the Fibonacci numbers.

[@MalevolentDivinity]

Ah, love random computer science examples that occasionally let me spot things instantly. When learning recursion, the specific example of why it could be bad was "You can make a method to get you any number of the Fibonacci sequence in one line of code, but doing so is a really stupid idea." Said line of code was return(method(x-1)+method(x-2));

[@aeqildonai]

I actually played with the formula at 10:20 to try to see how it relates to Binet's formula for a closed-form expression, and at first I didn't take into account that x0 = F1, but it fits perfectly except that you get n+1 in Binet's after expanding this. Pretty cool to see it derived!

[@pbenikovszky1]

The fact that they do not say the name Fibonacci until 11:19 is the coolest thing ;)

[@TheBigLou13]

I'm kinda proud that I anticipated the fibonacci sequence already at the 6:43 mark :D I liked the frog model to visualize the whole thought experiment :3

[@physicsjeff]

I stumbled onto all that beautiful mathematics years ago by playing Xenogears for playstation 1. The turn-based attack system utilizes the triangle, square and x buttons in a similar manner to frog leaps. I always thought it was a very unique and clever battle mechanic and I'm glad I took the time to count all the different ways of attacking back then and make all those connections and generalizations.

[@vincemclaughlin671]

I absolutely LOVE an answer this satisfying!

[@j_sum1]

Ok. I want frogs that can jump up to 5. Because the quintic has no general solution. That is when integer solutions to an equation become truly amazing.

[@omot4372]

Another great video on your channel! Thank you.

[@stevefrandsen7897]

Wow! Tom's best vid yet.

[@tectix0]

Would the sequence for 1, 2, or 3 jump sizes be called the Tribonacci numbers?

[@JesseUnderscoreMartin]

12:44 I calculated this by hand on the back of a napkin and he is indeed correct

[@zuhalter0071]

I was a Math major. I'm a little disturbed, but fascinated, by the way he draws X's, and sticks with parchment. I get it, but it isn't normal. Looks beautiful though! I sometimes make my symbols look artistic!

[@sakkikoyumikishi]

So, basically, it is very easy to find an upper bound for this (but it's a pretty big one): Define each jump of length 1 as 0. Define each jump of length 2 as 1. Each possible pattern of jumps is now represented by a unique binary number consisting of 50 to 100 digits, where each digit represents an individual jump. The upper bound is, therefore, 1267650600228229401496703205375 - which comes out as 100 times the digit 1 when expressed as binary. Now of course we know the actual number can't be this high, because if every jump were a jump of length two, then only 50 jumps could happen in total. But it gives us a very quick guesstimate for the kind of dimensions we're working with

[@Rank-Amateur]

If you state that the frogcs mate at the other side wants to see the frog do all possible combinations before arriving, you could have an interesting rephrasing that would require determining if the lillypad quantity is even or odd. When the number of lillypads is a multiple of three the frog will finish on the "wrong side" of the pond.

[@Dalroc]

Tom: It looks awful. Also Tom, just 25 seconds later talking about the very same expression: This is a really good example of the beauty of mathematics

[@Darkstar2342]

My approach was: For the first step, the frog can either jump 1 or 2 steps. If it jumps 1 step, it has then all the possibilities for 99 steps left. If it jumps 2 steps, it has all the possibilities for 98 steps left. So x_100 = x_99 + x_98 ... which leads to the same result, just not doing it "backwards" from the end but forwards instead, which I think is simpler and more straightforward...

[@Toobula]

The way it unfolded to me was to write the recursive function for X(n). The function would return 1 if n=0 or n=1, otherwise it would return 1 + X(n-2) [the frog starts with a jump of two, then completes with X(n-2) jumps] plus 1 + X(n-1) [the frog jumps 1 and completes with X(n-1) jumps.

[@screambmachine]

is there a way to calculate the number of ways to jump across, if any length of jump is allowed?

[@matejlieskovsky9625]

Yes. You can simply look at which pads you land on, giving you 2^(n-1) possible paths. The minus 1 accounts for having to land on the final pad.

[@andrewjmarx]

If you set the problem up as an adjacency matrix M and solve for the inverse of (I - M), then the first row/last column (depending on the direction you want to go) gives you total number of paths between nodes i and j. In other words, the first row/last column of (I - M)^{-1} will be the Fibonacci sequence.

[@benjaminshropshire2900]

1] For X total pads, you can skip up to floor(X/2) 2] If you are skipping S pads then you are making S 2-jumps and X-2S 1-jumps (a total of X-S). 3] There are (X-S) choose S ways to order the jumps. The above becomes a rather messy "factorials in a sigma" expression, but it's not too horrible to work with. And it will simplify the the same answer as in the video.

[@jodisel7364]

These frogs look soo lovely!!

[@paulchow611]

This exactlly was the problem demonstrating the dynamic programming when I was taking the Algorithm lecture in University. 🥰

[@daffers2345]

I think the frog's little froggy brain exploded from too many choices ... 😆🐸

[@Chalisque]

Back in 1992, the problem we were given to investigate for our GCSE coursework was like this, but adding 1's and 3's rather than 1's and 2's.

[@WahranRai]

Is it possible to approach this problem by Dynamic Programming (Richard Bellman)?

[@tfofurn]

I love when Brady asks my questions for me, like allowing a three-pad jump.

[@joshuascholar3220]

The way that an integer recurrence can be solved with square roots reminds me of one that Matt Parker posted the other day. if rand() is defined as a function that returns a random number from 0 to 1 then the square root of rand() gives the same distribution as the maximum of two rand() functions.

[@G5rry]

Great Numberphile video, but I'm also interested in the room this was filmed in. That table looks worn down by hundreds of years of use, and what kind of books are behind the cages? It would be an honour to work in a place with so much history.

[@IngieKerr]

it's St Edmund Hall Old Library, a college of Oxford University [where Tom is an Outreach Fellow ]... there's a 3d "wikispace" for it with a 360 interactive image so you can pan around. if you search for; _wikispace St Edmund Hall Old Library_ you should find it edit to add: looking at the wikipedia entry for the college, you'll also find the quote "the oldest surviving academic society to house and educate undergraduates in any university" - estimated to have been established by 1236, possibly earlier - so yeah :) quite a history :)

[@jpe1]

Two questions: given jumps of length 1 or 2 as discussed in the video, and assuming either length jump is equally likely, what is the expected value for the number of jumps? What if the frog can make a jump of any length (from 1 up to and including all the remaining lily pads) randomly chosen such that the probability of any particular length jump is equal. So, at the start, with 100 lily pads, it could jump 1, or 2, or 3, or … 100, each with the likelihood of 1/100. For example, let’s say 50 for the first jump, so now the next jump would be 1, or 2, or … 50, with 1/50 probability. Say the next jump is 21, now 1/39 for the remaining jump, say 13, now 1/16, say 8, now 1/8, say 3, now 1/5, say 4, now 100% chance of jumping 1 to the final lily pad. What is the expected value for the number of jumps?

[@koenth2359]

10:00 Same, but a bit more compact: (((1+R)/2)^(n+1) - ((1-R)/2)^n+1)/R with R=sqrt(5). From the binomial expansion it is clear to me that the even powered terms will cancel and from the odd powered, an even power of R remains after finally dividing by R.

[@DavidMay-cc1xo]

I know it's not fibonacci number related, but it's about that exponential growth. In my early days of learning a bit more advanced math, the teacher said something like "Let's say you have 3 books and you want to arrange them in every possible combination on your bookshelf. There are 6 different ways to arrange the, Now let's say you have 10 books to arrange in every possible combination, how long would it take you? Let's say it took you a 10 seconds to arrange the books in a new order." It seems almost simple, it's only 10 books, maybe a couple hours. But it would take over a year of continuously rearranging the books. And adding just 1 more book would now take over 12 years. (Yes, it's when I learned about factorial). That's why I love the idea of how many possible combinations can a deck of 52 cards be arranged in. It's such a stupidly large number that most people can't wrap their head around it.

[@94249]

5:28 when there are 4 lily pads, the 5 different ways the frog can jump are 1111, 22, 112, 211, 121. All of these numbers have the digit sum 4 and are only made of the digits 1 and 2. That means when there are n lily pads, the total number of ways the frog can jump is all the numbers written only using 1 and/or 2 that have the digit sum n. If we try this with n=3, the numbers would be 111, 12, 21. All of them have the digit sum 3 and are dont have any other digit than 1 and 2.

[@davecorry7723]

*Two* really nice moments. Though I didn't get why x98 + x99 = x100. x89 and x99 sound like huge numbers but only 1 jump away from x100, so I never would have thought they _sum_ to x100, instead I would have thought x98 + 1 = x100.

[@erikfinnegan]

Same question here. The ways to get to x99 seem to be a set that's largely contained in the set that solves x98. 🤔

[@ProfessorPolitics]

I had the same issue and had to do a bit more reading/thinking on it. Hopefully this will help! Let's simplify this down to the number of ways to get to 5 spaces. There are eight. a)2+2+1 b)2+1+1+1 c)1+2+1+1 d)1+1+2+1 e)1+1+1+1+1 f)2+1+2 g)1+2+2 h)2+1+2 Now let's look at the way to get to 4 spaces: i)2+2 j)2+1+1 k)1+2+1 l)1+1+2 m)1+1+1+1 Finally, let's look at all the ways to get 3 spaces: n)2+1 o)1+2 p)1+1+1 If you notice, all of the examples for getting 5 are actually ALL of the ways to get 3 and all of the ways to get 4 with just one additional step. 1) a = i +1 2) b = j + 1 3) c = k + 1 4) d = l + 1 5) e = m +1 6) f = n + 2 7) g = o +2 8) h = p +2 If you'll notice, 1)-5) are all of the ways you can go to pad 4 with an additional + 1 and 6)-8) are all the ways you can get to pad 3 with an additional + 2. This is what they mean when they say that the only way you can get to the 5th lilypad is to either be at the 3rd lilypad and make a jump of 2 or to be at the 4th lilypad and make a jump of 1. Any way that you could go from pad 3 to pad 5 by first resting at 4 is already encapsulated by all the ways you can get to pad 5 via pad 4---because all of the ways to 4 necessarily include any permutation where the penultimate move is at 3. Trying to include again would be tantamount to double counting. More concisely: The number of routes to X_n is the same as the number of routes to X_{n-2} plus the number of routes to X_{-1}---but the individual unique sequences are necessarily elongated by the addition of a +2 and +1, respectively.

[@TheWhite2086]

@@erikfinnegan It might be easier to visualize if you go back to x3=x2+x1 x1 is 1 x2 is 1,1 or 2 x3 is 1,2 or 1,1,1 or 2,1 1,2 is just x1 and an extra jump of 2 1,1,1 and 2,1 are both x2 and an extra jump of 1

[@veessee]

Can someone explain at 8:30, why x(n) = A(λ+)^n + B(λ-)^n ? Why is it not just x(n) = (λ+)^n, or x(n) = (λ-)^n, since those are the solutions of the quadratic equation? Where did A / B come from?

[@plislegalineu3005]

Multiplying the equation (L^n - L^(n-1) - L^(n-2) - ... - 1 = 0) by (L-1) gives (L^(n+1) - 2 L^n + 1 = 0)

[@snowkracker]

The total number of ways blew my mind.

[@Fuzeha]

(Haven't watched the soln yet) Assume there are S_(n-2) ways of hopping to stone n-2, S_(n-1) ways of hopping to stone n-1. Any path to stone n must land on either stone n-1 or n-2. If it lands on n-1, there is only one way of getting to n, ie just jumping one space, so S_(n-1) paths to stone n hit stone n-1. Alternatively, if the frog lands on n-2. It has two options, jumping to stone n-1 and then stone n, or jumping directly to stone n. However the former is accounted for in the S_(n-1) ways of getting to stone n via n-1, so we count S_(n-2) ways of getting to stone n via n-2 (pv we don't use stone n-1) In total, S_n = S_(n-1) + S_(n-2). Since S_0=1 and S_1=1, we conclude that S_n is the nth Fibonacci number.

[@TerribleShmeltingAccident]

my favorite math meme is a photo of a smiling bill cosby with the caption “tan(b)/sin(b) = “

[@Ninterd2]

I won't say anything about what that drawing on 3:39 looks like, butt I will say I'm immature enough to be distracted by it.

[@robertpearce8394]

Come on Brady, you already know about the Golden Ratio relationship from the Brady Numbers.

[@endrankluvsda4loko172]

This was very cool! My intuition was to guess 2 to the power of 100 since each pad has 2 states as in having or not having the frog and there's 100 of them. I would have never guessed there's a relationship with the Fibonacci sequence. Then again, I'm not as mathy as I used to be. Thank you for sharing. And Tom's a pretty cool guest. Nail and Gear forevah!

[@iume4801]

If it takes 1 second per leap across the pads for a 1 or 2 long jump then how long would it take a frog to jump all possible combinations when n=100? E.g., jumping 2,2,2,2,2,2,2... is 50 seconds (50 jumps) but 1,1,1,1,1,1,... is 100 seconds.

[@BennyTheBrain]

It would take the frog 41544212574050115730575 seconds, which is 1317358338852426 years, 108 days, 17 hours, 36 minutes and 15 seconds.

[@iume4801]

So it would take roughly 100000x longer than universe has existed to try all combinations at a rate of 1 second per leap for 100 lilypads. Oof. Really big numbers indeed.

[@ericmckenny6748]

Ello! From the other side of the pond.

[@ci.netproductions]

The entire video I was screaming to myself, “FIBONACCI!!! GOLDEN RATIO!!! φ!!! MY FAVORITE NUMBER!!!”