# Solution 59: Recursion and Hidden Fibonacci Sequence

Share
Embed
• Published on Sep 27, 2018
• We use creative counting methods--recursion and one-to-one correspondence--to count the number of 9-digit (and 2001-digit) integers that satisfy the constraints.
Congratulations to Walker Powell, attyfarbuckle, Kevin Tong, GreenMeansGO, CymoTec, Seth Harwood, Nicola C, Sean Skelly, SeongKyun Jung, and Bigg Barbarian for successfully solving this math challenge question! Walker Powell was the first person to solve the question.
Your support is truly a huge encouragement.
Every subscriber and every like are wholeheartedly appreciated.

• LetsSolveMathProblems  10 months ago +17

*At 9:13 and 12:25, I should have written 38, NOT 39. I sincerely apologize for such an elementary error (in division by 2, out of all potential mistakes; sigh...). This may be the most glaring, silly mistake I have made so far. Hopefully it does not detract too much from the main argument of the video. =)

• Henry M. 8 months ago +1

a bit late to the party, but here's a 2-liner in python:

import itertools
len([x for x in itertools.product(range(1,4), repeat=9) if all((x[k]>x[k-1] and x[k]>x[k+1]) for k in range(1,9,2)) and x[::-1]>x]) #this is why you should learn python
btw, F10+F9=F11 and F2002+F2001=F2003 ;)

• This video just reinforces the stereotype that Asians are good in math (and are nerds).

• adandap 10 months ago +2

Very very nice. Looking at the several pages of notes I wrote while unsuccessfully trying this problem while sitting on a train, I see the word 'palindrome', a correct counting of the 3 and five digit numbers... and nothing helpful beyond that. The idea of setting up a couple of difference equations never occurred to me. But I can divide by 2 accurately, so there's that. :D

• LetsSolveMathProblems  10 months ago +1

Perhaps I should review division worksheets from elementary school. =)

• Amit Kumar 10 months ago

Sir,would u tell me how do u make effective thumbnails for ur videos??

• Sajid Rizvi 10 months ago +2

This was soo good!

• Tony James 10 months ago

One quick note. When you gave the answer formula using Fibonacci numbers you can reduce it a bit further
F10 + F9 = F11
- F6 - F5 = -(F6 + F5) = -F7
Putting that together:
(F10 + F9 - F6 - F5) / 2 = (F11 - F7) / 2
In general, the solution for a number with n digits (where n is odd) would be [F(n+2) - F((n+5) /2] / 2

• David Franco 10 months ago +2

cool.
I also solved with a program, but I don't use 9 nested for-loop, just 2 XD
(well 4 if you count the auxiliary function)

• Boris Valderrama 10 months ago +2

awesome

• Mertianyiva 10 months ago +3

first yay :)