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.

[@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.

[@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]

😎😎😎

[@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.

[@GeorgeCilley]

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

[@TomRocksMaths]

can confirm.

[@528Circle]

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

[@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.

[@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.

[@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.

[@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.

[@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.

[@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

[@j.vonhogen9650]

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

[@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.

[@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

[@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.

[@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

[@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]

😂

[@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

[@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.

[@Rubrickety]

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

[@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!

[@polyaddict]

2:11 I love the showcase of the Parker frog

[@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!

[@AnirbanBanerjee-xm8cr]

This combinatorics problem is just awesome!

[@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.

[@johnchessant3012]

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

[@0xero7]

CS majors having leetcode flashbacks rn

[@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).

[@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

[@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.)

[@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.

[@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.

[@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. 😔

[@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??" 🤣

[@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.

[@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!

[@tectix0]

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

[@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.

[@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!

[@wentbackward]

This is one of my most favourite numberphile videos.

[@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?

[@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.

[@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.

[@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.

[@WahranRai]

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

[@Lashb1ade]

I first encountered this problem years ago in university as a "tiling problem" - you have rectangular tiles of size 1x2, how many ways are there of tiling a strip of floor 2xn long. There was the same extra credit problem - "what if you have 1x3 tiles on a 3xn floor?" only that resulted in the interesting sequence x(n-3)+x(n-1)=x(n). If you have both 1x3 and 1x2 tiles, things get quite complicated, as you can have a block of 6 length that could be either two threes long or three twos long. It was an interesting problem I would recommend Tom look into it.

[@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

[@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.

[@beirirangu]

What if only jumps of 2 or 3... there is a difference of 1 so all numbers except 1 will be possible... so the sequence would be... 1,0,1,1,1,2,2,...? AKA Xn=X(n-2)+X(n-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.

[@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));

[@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.

[@joebloggs3551]

I really love that room.

[@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?

[@vincemclaughlin671]

I absolutely LOVE an answer this satisfying!

[@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 :)

[@cndbrn7975]

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

[@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

[@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.

[@1curiocat]

A related problem that I cannot figure out is this. Start with a row of n skittles (the small bowling pins not the candy). In each move you take away a single skittle or two side-by-side (no gap between them). How many ways can you clear away the row?

[@Tumbolisu]

If you do not care about the order in which the skittles are taken away, then you have the exact same problem as the frog on lily pads, resulting in the fibonacci numbers. However, if you consider a different order of moves to be a different way of clearing the row, then you will obviously get much bigger numbers. Basically, it's like the frog on lily pads problem, but each individual way of crossing the lake is multiplied by the number of ways that this number of jumps can be "re-arranged", which is the factorial of that number. So, we get: 1 skittle: 1 way: (1) -> 1 = 1! 2 skittles: 3 ways: (1,2), (2,1), (1+2) -> 2 + 1 = 2! + 1! 3 skittles: 10 ways: (1,2,3), ..., (3,2,1), (1+2,3), (3,1+2), (1,2+3), (2+3,1) -> 6 + 2 + 2 = 3! + 2 × 2! 4 skittles: 44 ways: (1,2,3,4), ..., (4,3,2,1), (1+2,3,4), ..., (4,3,1+2), (1,2+3,4), ..., (1,2,3+4), ..., (1+2,3+4), (3+4,1+2) -> 4! + 3 × 3! + 2! 5 skittles: 5! + 4 × 4! + 3 × 3! = 234 ways 6 skittles: 6! + 5 × 5! + 6 × 4! + 3! = 1470 ways ... n skittles: According to OEIS A240172, we should get: Sum[Binomial[n-k, k] * (n-k)!, {k, 0, n}] (you can paste that into Wolfram Alpha with n replaced with a number) or in English: The sum from k = 0 to n of: (n-k chose k) times (n-k)! Note that if k gets bigger than n/2, the binomial (n-k chose k) becomes zero, which means that term of the sum is eliminated. Each factorial corresponds to a specific number of double-hits. For instance, for 4 skittles, the "4!" corresponds to only removing one skittle at a time, the "3!" corresponds to removing two skittles at once one time, and finally the "2!" corresponds to removing two skittles at once two times. An extra factor is added if there are multiple choices for which skittles to double-hit. (There are 3 choices for getting 1 double-hit with 4 skittles: 1+2, 2+3, or 3+4.)

[@Tumbolisu]

Super short answer: Go to OEIS A240172

[@stevefrandsen7897]

Wow! Tom's best vid yet.

[@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.

[@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.

[@igorbartoshuk9762]

The most decorated mathematician I ever saw. Respect.

[@omot4372]

Another great video on your channel! Thank you.

[@tomushy]

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

[@brightmatter]

I remember figuring out the iterative form of the Fibonacci, because I wanted to display a visual Pascal's Triangle (and highlight the angled Fibonacci in it, as well as the total) in a browser, but the recursive approach ran me out of memory too fast and my visual triangle was boring due to how small it was. By moving to the iterative, I was able to make a very large triangle such that the next problem was space to hold the giant numbers at the bottom of the triangle.

[@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).

[@MrPejotah]

Instead of recursion, I used combinatorics, arriving at: Total number of ways to cross = sum i=0->50 of (100-i)Ci Exactly same answer :) I wonder if there's a way to go about the problem with Markov Chains.

[@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.

[@ddturnerphd]

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

[@markdatko4832]

Of course you can extend the size of the jump j in N, what about backwards j in Z or transfinite j in Ord ?

[@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!

[@ErikLeppen]

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

[@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.

[@benreeves1908]

We studied this problem in my discrete mathematics class in my CS degree, but it was presented as the "rod cutting problem." How many ways are there to cut a rod into segments of sizes 1 or 2?

[@erichbaumeister4648]

At 13.50 you list jumps from pads 99, 98 and 97. Does that take into account that there are two ways from 97? (1 pad then 2 pads or 2 pads then 1)

[@pattoner8398]

So Fibonacci numbers have the golden ratio in that lambda formula, what value is obtained by solving the Tribonacci formula, and how does that number change for increasing values of jumps (can jump up to 4 lilly pads, 5, etc)?

[@davidgillies620]

Interestingly, if you allow hops of any size up to n, the number of ordered partitions of n becomes simply 2^(n - 1).

[@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.

[@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.

[@bluekeybo]

4:00 shouldn't it be x98+x99+1=x100? Cause you still need 1 more jump to get to x100?

[@eruwa1550]

No because you're not counting # of jumps, you're counting # of ways to get to 100. The final jump doesn't change the # of ways to get there

[@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!

[@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.

[@johnwaugh5372]

Before I even noticed the fibonnacci connection I was looking at the problem statement through combinatorics and got an equation involving the summation from 0 to floor(n/2) of an expression involving factorials, which I guess somehow turns out to be equivalent (not too weird when you consider taylor expansions are a thing).

[@johnwaugh5372]

Specifically the formula I arrived at was \sum_{k=0}^{\lfloor n/2 floor}\frac{(n-k)!}{k!(n-2k)!} (though I'm guessing this is probably something that's already known)

[@wasistderunterschied3273]

Tried to solve a problem kinda similar to this some time ago. Rules: 1. Random jump-distance 1-6, 2. Fixed distance to target (e.g 100), 3. Some lillypads are missing (you lose if you step on them) - fixed layout (e.g: Lillipad 3,15, 30 are missing). I tried to calculate the chance of winning - ended up simulating it to get a close estimate. Still no clue to this day how to solve this.

[@textboxdesign]

So how many possible ways would be there if this frog had superpowers and could jump not only 1 or 2 but any number „j” from 1 to n. Could the X(j,n) be derived from X(j-1,n) like we did for X(n) based on X(n-1) and X(n-2)?

[@erawanpencil]

What's that book jail /grille stuff on the wall? Would like to buy some but don't know what it's called.

[@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.

[@jodisel7364]

These frogs look soo lovely!!

[@frankharr9466]

Hm. What ratio comes up with the sum of the previous 4 numbers? Is there a Numberphile 2 video on this or why not?

[@BugBestieLily]

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

[@daffers2345]

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

[@Eagle0600]

While you were talking about x2, I was thinking about x0=1. That set the sequence up to be 1,1,2,3. I believe x4=5. I wonder if the final result will be the Fibonacci sequence. edit: Just seconds later you talk about the conditions to reach lilly-pad number 100, being either a jump of 2 from 98 or of 1 from 99, and now I'm absolutely certain the sequence is simply the Fibonacci sequence.

[@RibusPQR]

And the number of ways to get to -1 is zero, since the frog cannot jump backwards.

[@MrJBB89]

step by step, how do you get to 1+λ=λ^2 by "dividing all that by λ^n-2" as is said around 7:47?

[@WK-5775]

Because t^a / t^b = t^(a-b). Apply this to each term with b=n-2 and a=n-2 or n-1 or n, respectively (and, of course, t=lambda).

[@MrJBB89]

@@WK-5775 I see it now, many thanks

[@ericmckenny6748]

Ello! From the other side of the pond.

[@robertpearce8394]

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