Solution 59: Recursion and Hidden Fibonacci Sequence

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.

[LetsSolveMathProblems]

*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. =)

[adandap]

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

[micomrkaic]

Super clever solution. Thank you for the video.

[RasperHelpdesk]

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

[copperfield]

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)

[henrym.]

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

[AmitKumar-homr]

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