Solution 59: Recursion and Hidden Fibonacci Sequence

  • 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.

Comments • 11

  • LetsSolveMathProblems
    LetsSolveMathProblems  8 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.
    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!

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

  • adandap
    adandap 8 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

  • Amit Kumar
    Amit Kumar 8 months ago

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

  • Sajid Rizvi
    Sajid Rizvi 8 months ago +2

    This was soo good!

  • Tony James
    Tony James 8 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
    David Franco 8 months ago +2

    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
    Boris Valderrama 8 months ago +2


  • Mertianyiva
    Mertianyiva 8 months ago +3

    first yay :)