Catalan Numbers Enumeration of Lattice Paths and visual Recurrence Formula (synthwave)

If you like this video, check out my others and consider subscribing. Thanks!

00:17 Enumerate all restricted lattice paths from (0,0) to (a,a) for a up to 7.
01:37 Visual proof of recursion formula for Catalan numbers

#catalannumbers #catalan​ #mathvideo​ #math​ #mtbos​ #manim​ #animation​ #theorem​​ #visualproof​ #proof​ #iteachmath #mathematics #binomialcoefficients #latticepaths #discretemath #combinatorics #enumeration #synthwave #recurrence #quadraticrecurrence

To learn more about animating with manim, check out:
_________________________________________
Music in this video:

[Mutual_Information]

woo!! Keeping going! The channel is improving - looks great!

[heavysaur]

C(n) = nCr(2n, n) - nCr(2n, n+1) very interesting !
You can find that formula by saying that any lines that pass below the diagonal lines are all the lines that can go to (n+1, n-1). Why ?
Well take any path (that finish at point (n, n)) that goes bellow the diagonal line, so that it hit a point (x+1, x). Now take the segment of the path after that point (x+1, x) and mirror it with respect to the diagonal line (the y = x line).
You can then see that the path will then hit the point (n+1, n-1). So we can say that:
C(n) = (any path that goes to (n, n)) - (any path that goes to (n+1, n-1))
C(n) = nCr(2n, n) - nCr(n-1 + n+1, n+1) = nCr(2n, n) - nCr(2n, n+1)