# Solution 59: Recursion and Hidden Fibonacci Sequence

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.

Please take a second to subscribe in order to send us your valuable support and receive notifications for new videos!

Every subscriber and every like are wholeheartedly appreciated.

LetsSolveMathProblems8 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.6 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 ;)

Abolish Roe v. Wade, not ICE!6 months agoThis video just reinforces the stereotype that Asians are good in math (and are nerds).

adandap8 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

LetsSolveMathProblems8 months ago^{+1}Perhaps I should review division worksheets from elementary school. =)

Amit Kumar8 months agoSir,would u tell me how do u make effective thumbnails for ur videos??

Sajid Rizvi8 months ago^{+2}This was soo good!

Tony James8 months agoOne 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 Franco8 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 Valderrama8 months ago^{+2}awesome

Mertianyiva8 months ago^{+3}first yay :)