Solving Polyn Eqns 14: Recursive
Wild Egg Maths
4.44K subscribers
Catalan numbers and Fuss numbers form the vertical and horizontal borders of the BiTri numbers, which are sub multinomial numbers of a particular kind that seem to crop up naturally, if magically, by looking for power series solutions of cubic equations.
We want to understand the local nature of these BiTri numbers, in particular as we move down and right in the array. For this certain inductive or recursive relations come into view.
00:06
joining me on this adventure
00:07
towards solving polynomial equations
00:10
we've outlined a
00:12
potentially important conjecture which
00:14
we're calling the by tri conjecture
00:16
which concerns these interesting sub
00:20
multinomial numbers which we're calling
00:22
by tri numbers
00:23
so let's define cmn is 2m plus 3n
00:26
factorial
00:28
over 1 plus n plus 2n factorial m
00:30
factorial
00:31
n factorial this is
00:34
a number which although it looks like a
00:38
rational number
00:39
it seems at as if it's going to be
00:41
always a natural number and the by tri
00:45
conjecture is an explanation for that it
00:48
claims that this number actually counts
00:50
the number of diagonal subdivisions of a
00:53
2
00:54
plus m plus 2n sided polygon
00:57
into m triangles and n
01:00
quadrilaterals and here are these
01:03
numbers in an array
01:04
with m going down this way n going
01:07
across
01:08
and both indices starting at zero
01:12
and just a little bit further down here
01:14
is a corresponding array
01:16
of polygon sizes
01:20
okay where we're looking at the sizes of
01:23
the polygons that are
01:24
involved in the subdivisions here so for
01:26
example the catalan story we're
01:28
subdividing
01:30
a two gun a three gun a four gun a five
01:32
gone a six gun etc
01:34
if we go over in this direction we're
01:36
going up two so
01:38
two four four gone six gone
01:41
eight god et cetera if we're going down
01:43
here well it's one in this direction two
01:45
in this direction so this is
01:46
five that's a two plus one plus two
01:49
that's a five gone
01:51
seven gone and i'm gone etcetera
01:55
okay so this is i think a really
01:56
tantalizing conjecture because it
01:59
combines
01:59
our very familiar story with the catalan
02:02
numbers here
02:03
and also across this first row with what
02:06
we've been calling the fuse
02:08
catalan numbers um i may start to
02:11
actually
02:12
change that a little bit i i think that
02:15
foose doesn't get enough credit for this
02:17
fuse was an important assistant to
02:20
leonard euler
02:21
and i think so his contribution just by
02:24
helping euler is really quite immense in
02:26
terms of you know affecting modern
02:28
mathematics
02:29
and he was around a long time before
02:30
catalan so we might start calling
02:32
this top row here the foos numbers if i
02:35
start doing that
02:36
you'll know why okay so what we want to
02:39
do
02:39
is we want to try to
02:43
get some some basic starting points some
02:46
handles on how we might
02:48
attack this conjecture and one way of
02:52
doing that is to look at the form
02:54
of these these numbers and see what kind
02:58
of inductive
02:58
relations they have as we go
03:02
down the columns and across the rows
03:04
okay
03:05
so today we want to
03:09
investigate possible
03:13
inductive or maybe recursive another way
03:16
of thinking about it
03:17
recursive relations between
03:20
the cmn
03:24
particularly as we
03:27
go down columns and
03:31
across rows this is kind of a
03:34
two-dimensional inductive situation
03:36
right where
03:37
we're trying to explain this entire
03:39
array not just one row or one column
03:41
but nevertheless it's a good starting
03:43
point to try to understand what happens
03:45
as you go down
03:45
columns or go across rows
03:49
so natural place to start is with the
03:52
first column actually the zeroth column
03:55
okay the zeroth column
03:59
the catalan story so let's uh say
04:02
c m
04:05
that'll be uh same thing as c m zero
04:09
and let's take our formula
04:12
and just we have to get used to this
04:15
formula okay it's kind of interesting
04:18
so let's put it there okay and we're
04:19
going to replace n
04:21
with zero that's meaning the zeroth
04:26
column the n's just disappear
04:29
n factorial 0 factorial same as 1
04:33
and this thing disappears and so that is
04:35
indeed the usual
04:36
catalan story and
04:40
now let's ask you know what is the
04:41
relationship between successive
04:44
elements in this column okay so
04:47
the relation between
04:51
successive elements
04:52
[Music]
04:55
is let's try to establish this so let's
04:58
look at
04:59
c of m plus one say okay so that's going
05:02
to be
05:04
same kind of fraction
05:08
but instead of having m here we
05:11
replace the m with 2 with m plus 1 so
05:15
that will give us 2 m plus 2
05:16
in that factorial on the top and instead
05:19
of having m plus 1 here then we're going
05:20
to have
05:20
m plus 2 so we'll write 2 plus m instead
05:23
of having the m we'll have an m
05:25
plus 1 which we might just write as 1
05:26
plus m
05:29
okay and now let's relate this you know
05:32
this is
05:33
something times like it's x
05:36
times
05:43
this the nth one and what is this x so
05:45
i'm going to replace this x with what it
05:46
is
05:46
i have to put a fraction here what do i
05:48
have to put in here
05:50
um so in order for things to be equal
05:52
there's a 2m plus 2 factorial
05:54
so there's also going to be a 2
05:58
actually probably to be consistent i
05:59
should put that 2 on the right should i
06:01
because i'm generally liking to put the
06:03
constants
06:04
first i want to try to be somewhat
06:07
consistent about that
06:08
okay so here we have 2 plus 2m that's
06:10
the first
06:11
term and or the top term in this
06:14
factorial and then the next one would be
06:16
1 1 plus
06:20
2m okay and then there'll be a 2m
06:22
factorial so that takes care of the
06:24
numerator and then in the denominator we
06:27
have to put some additional terms 2
06:29
plus m and the other one is
06:33
just one plus m
06:36
does that look like a true identity
06:41
two plus two m factorial is two plus two
06:43
m times one
06:44
[Music]
06:45
plus two m times 2m
06:49
factorial yes and 2 plus m factorial is
06:52
2 plus m times 1 plus n factorial
06:54
and 1 plus m factorial is 1 plus m times
06:56
n factorial i think that's sick right
06:58
so we can now rewrite this as
07:03
that constant times well the
07:06
nth one okay
07:09
so we get let's record this
07:14
here's a kind of inductive
07:17
approach to the catalan numbers
07:26
now actually if we stare at this for
07:28
just a second we see that
07:30
this can actually be simplified because
07:33
this thing here this factor 2 plus 2m
07:36
actually has
07:37
a 2 can be pulled out front and if you
07:39
pull that 2 out then you have a 1 plus m
07:41
which will cancel with that one on the
07:42
bottom
07:43
so actually speaking there's a small
07:46
little
07:46
happy coincidence that happens here we
07:49
can factor the 1 plus
07:50
m here and essentially here giving us
07:54
the 2.
07:55
you don't need that bracket anymore all
07:57
right so um
07:59
maybe we could just actually just do
08:00
that all in one step
08:02
okay so that's actually the the
08:05
recursive relation
08:06
between cm plus 1 and
08:10
cm
08:13
we might note that uh
08:18
note that we could
08:21
rewrite this as
08:25
you know if we sort of got rid of the
08:27
fractions two plus
08:28
m times c m plus one
08:32
equals two times one plus two
08:35
m times c m
08:41
because i don't always trust myself let
08:43
me just check this okay so check
08:45
if say m equals 3
08:49
what's the third catalan number um
08:55
i'm just going to grab this thing here
08:58
get my computer to
08:59
calculate this for me so if i get rid of
09:02
that make that a definition
09:05
and then i evaluate
09:09
c of three that's equal to
09:12
five okay and of course we know what c
09:15
of four is but let's just check
09:17
c of four is fourteen so let's
09:20
see if the relation is correct the
09:22
relation
09:23
becomes okay uh
09:27
two plus m so m is three so that's five
09:30
times c m plus ones that's c
09:33
four so 5 times 14 equals 2
09:37
times 1 plus 2m
09:40
that's 7
09:44
times and cm is c3 which is
09:48
- uh which is correct
09:55
it's a good idea when you're making
09:58
these little calculations and canceling
10:00
things and so on
10:01
to check your formulas periodically
10:04
okay we have a tendency to get
10:06
enthusiastic
10:07
and to you know go fast and we make
10:09
mistakes
10:10
and then after a while if you allow that
10:13
mistake to
10:14
you know accumulate for a while you
10:16
finally you recognize
10:18
that something is fishy is going wrong
10:20
and then you've made a mistake but
10:21
it's a long ways back to the last time
10:23
you checked so it's good to
10:25
check periodically to make sure that
10:27
we're on the right track
10:30
okay so this relation actually is is
10:33
quite a famous relation so this relation
10:35
goes back to euler
10:37
and uh you know euler had to to prove
10:40
this kind of formula that the number of
10:42
subdivisions of a of a polygon
10:46
into m triangles was given by this this
10:48
catalan number
10:50
and so you know the the way
10:53
to do that or one way to do that is to
10:54
do it inductively and to
10:56
to use this relation between the nth
10:59
catalan number and the m plus first
11:01
catalan number
11:02
and to show that the the actual physical
11:05
subdivisions the number of subdivisions
11:07
actually respects this kind of law
11:09
right that's sort of one way of
11:11
establishing the fact
11:13
that the number of subdivisions is
11:14
actually given by this formula and not
11:16
something else
11:18
so you have to establish the recursive
11:19
aspect of course you also then have to
11:21
you know
11:22
check at a base case uh you know when
11:25
m is equal to one or zero or wherever
11:27
you're starting from
11:29
okay so that's that's kind of
11:32
good so now let's um let's generalize
11:35
this
11:36
so let's
11:39
let's generalize this and go down
11:44
a more general column not just the first
11:48
one
11:50
okay so what am i proposing to do so i
11:52
want to write
11:54
c of m plus 1
11:58
n so now the general element in our
12:00
array the general bitry
12:02
number with indices m plus 1 and n
12:05
i want to write it as something
12:09
something let's say like that something
12:11
times
12:13
c m n
12:18
okay so that's that's the kind of thing
12:19
that we want and i have to figure out
12:21
what this
12:22
something is okay
12:25
so let's try that out so let's see of m
12:29
plus 1
12:32
n what is that we have to go back to
12:36
our formula there it is there
12:40
there's cmn
12:44
and if i want to replace m with
12:47
m plus one what's going to happen so
12:50
this m here is replaced with m plus one
12:52
that'll give me a two out front
12:55
this m here replaced with m plus one
12:58
that'll give me a two out front
13:00
and this m replaced with m plus one give
13:02
me a one out front
13:05
okay and now i have to write that as
13:08
something times
13:12
um yeah the same thing that i
13:15
already used there we go again
13:21
okay all right that thing there is
13:24
this this last term is cmn and now i
13:27
want to figure out what this
13:31
required factor is so what do i have to
13:33
put in here
13:35
in order for this to be a legitimate
13:39
equality i might make this bigger so you
13:41
can
13:42
see it okay
13:45
okay what do we have to put in here so
13:47
on the numerator we have 2 plus 2m plus
13:49
3n factorial
13:50
and that's something times 2m plus 3n
13:54
factorial
13:54
so the extra terms that we have here
13:58
are going to be 2 plus 2m plus
14:02
3n uh that's the first one
14:06
and then a similar one
14:09
a similar one with instead of having a 2
14:11
having a 1.
14:14
okay now the numerators agree 2 plus 2m
14:16
plus 3n factorial it's the product of
14:18
all the number is less than or equal to
14:20
that one
14:20
there's that the number itself there's
14:22
one less and then all the remainders
14:24
are just encased in this 2m plus 3n
14:28
factorial
14:29
okay now we go to the denominators the 2
14:31
plus m plus 2n
14:33
factorial comparing that with this one
14:35
we need to put in an extra factor of
14:37
2 plus m plus 2n
14:44
the 1 plus m factorial we need to
14:47
put a factor of 1 plus m there
14:51
so now this 2 plus m plus 2 n factorial
14:54
is indeed the product of this term and
14:56
this factorial the one plus m factorial
14:59
is indeed
15:00
the product of the one plus m and the m
15:02
factorial and the n factorial is
15:04
captured over here
15:06
okay so what we're getting is that this
15:08
is then equal to
15:14
that times c m
15:17
n
15:21
now in the previous case the catalan
15:23
case we had some cancellation remember
15:25
the 1 plus
15:26
m kind of canceled any kind of
15:30
cancellation going on here
15:32
no it doesn't look like it looks like
15:34
this really is a
15:35
product of sort of quadratic things in
15:37
the numerator
15:38
divided by quadratic things in the
15:40
denominator
15:43
so what is this telling us this is
15:44
telling us an inductive
15:46
way of going down any column going down
15:48
the nth column
15:50
okay so this would be one approach to
15:53
solving this conjecture is to
15:55
is to just just figure out what happens
15:58
when you
15:58
start at the the top row which is the
16:00
first row okay
16:02
where we're subdividing a polygon into
16:04
purely quadrilaterals
16:06
and we assume we know the number that's
16:09
that
16:09
what we're calling the foose number and
16:11
now we have to investigate what happens
16:13
when we go down the corresponding column
16:15
that is
16:16
we're going to add triangles excessive
16:18
triangles
16:20
okay so so
16:23
if you can prove that adding
16:28
triangles to the
16:33
uh well the starting configuration
16:39
of having a decomposition
16:44
of just n quadrilaterals
16:50
if you can prove that adding triangles
16:51
to the starting configuration of having
16:53
decomposition incredibles
16:55
obeys this
16:58
recursion
17:03
then that will then
17:06
that will prove that
17:10
by try conjecture
17:16
right so you see the power of this um
17:19
it's a happy situation here this this
17:21
array has a lot of structure
17:23
the fact that the formula for all the
17:25
entries of this array are sort of
17:26
similar
17:27
means that there's these relatively
17:28
simple multiplicative
17:30
connections between elements in the
17:33
array
17:34
as we sort of go down or go across
17:38
okay so now let's have a corresponding
17:41
analysis
17:42
of rows let's
17:46
correspondingly look
17:49
at the rows starting of course
17:52
with the zeroth
17:55
row which we're now calling the
17:58
foose numbers okay
18:03
and let's grab our formula
18:06
there's our formula for the general one
18:09
and what are the foos numbers
18:14
formerly called the foose catalan
18:15
numbers now we're thinking about calling
18:17
them foose
18:18
numbers and uh so the catalan numbers
18:20
were sort of
18:21
c's um let's use f's that doesn't
18:25
sound too unreasonable does it so let's
18:26
say f of
18:28
n equals so there's the
18:31
the usual the general formula but now
18:33
it's the case when
18:35
m is equal to zero okay so
18:38
maybe i should write that it's it's c of
18:40
m
18:42
zero which is no sorry that's not
18:45
correct it's
18:45
c of zero n
18:49
m m is equal to zero that's the number
18:51
of triangles
18:52
n is the number of quadrilaterals that's
18:54
n okay so we have to set
18:56
m equal to zero get rid of that m
18:59
get rid of that m get rid of this m
19:02
factorial because that's just
19:05
one
19:08
okay so those are the foos numbers and
19:11
so they satisfy
19:16
the relation with a recursive relation
19:21
let's look at f of m plus one
19:25
okay sorry n plus one
19:29
yes f of n plus one and so we're going
19:31
to grab this and i'm gonna replace
19:33
n with n plus one so n
19:36
is replaced with n plus one so that top
19:38
will give us a three plus three n
19:42
and this n is replaced with n plus one
19:46
uh that gives us uh two times
19:49
n plus one that's adding two so i think
19:51
that's also three
19:52
plus two n and we're saying that we're
19:56
replacing this
19:57
n with n plus one so that will become a
19:59
one plus n
20:00
all factorial
20:04
okay so that's f n plus 1. and we want
20:08
to write it as say
20:09
something times f of
20:12
n which is the something
20:15
times the nth one it's just this one
20:21
okay and what is that shouldn't be too
20:23
hard to do so it's
20:25
something
20:28
times this and what is that something
20:30
it's some kind of fraction
20:31
so uh in the numerator we have three
20:33
plus three n factorial
20:36
so when we expand that out the first one
20:37
will be three plus three n
20:40
then we have to multiply by the one less
20:41
than that two plus
20:43
three n one less than that
20:46
one plus three n one less than that
20:49
is three n and so after that the three n
20:52
factorial
20:53
accounts for all the product of the
20:54
remaining terms so these three terms now
20:58
um make the the numerators
21:02
match up what do we have to stick here
21:04
in the denominator there's a 3 plus 2 n
21:06
factorial that we want to capture
21:08
here there's a 1 plus 2 n factorial that
21:10
we want to capture
21:11
so we're going to put 3 plus 2
21:15
n and then remove or
21:18
reduce that by one two plus two n
21:21
and then the one plus two n is will be
21:23
captured by this one
21:24
and finally the one plus n factorial we
21:26
already have an n factorial
21:27
means we have to add another one plus n
21:31
here
21:35
okay that's all right now
21:38
what um okay we could
21:42
simplify this just a little bit because
21:45
the same kind of thing happening that uh
21:48
happened in the
21:49
catalan story there's a 1 plus n here
21:51
and that's also a factor of this term
21:53
here 3 plus 3n
21:54
so if we make a mutual cancellation
21:56
we're going to get a 3 there
21:58
and this term down here is going to
21:59
disappear
22:02
and are there any other cancellations 2
22:04
plus 3 and 1 plus 3n
22:05
3 plus 2n 2 plus 2n
22:10
that looks like what it is and so this
22:12
thing here is f sub n
22:15
and that looks like a recursive relation
22:19
for
22:19
our fuse numbers now i'm confident this
22:22
is well known
22:24
okay this will be well known in fact we
22:26
probably look on the
22:27
online encyclopedia to find that it's
22:29
somewhere in the information about the
22:31
about that foose catalan or foose number
22:34
entry
22:35
and so that means that if we want to you
22:37
know establish
22:39
the the geometrical interpretation of
22:42
the foose numbers
22:44
in terms of numbers of subdivisions of
22:48
appropriate polygons into quadrilaterals
22:51
we would want to explain
22:55
why that geometrical numbers
22:59
why those geometrical numbers satisfy
23:01
this recursive
23:02
relation why the number of ways of
23:05
subdividing such a polygon into
23:07
n plus 1 quadrilaterals is equal to the
23:09
number of ways of subdividing
23:11
into n quadrilaterals times this
23:14
particular factor which is
23:15
quadratic both in the numerator and the
23:18
denominator in
23:20
n
23:23
so it is already a challenge
23:28
to prove that
23:31
the subdivisions
23:36
of um let me just remind myself what the
23:39
polygon is
23:40
it's a 2 plus m plus 2n okay so
23:43
that the subdivisions of a
23:46
2 plus 2n gone
23:50
into n quadrilaterals
23:55
that's our foose catalan number
23:59
f of n
24:02
satisfies this
24:06
recursion
24:12
now with the catalan story i more or
24:14
less explained that
24:15
in that video i mean it's well known
24:17
goes back to euler
24:18
uh in this foos story i don't really
24:22
know how this goes
24:23
i've thought a little bit about this but
24:24
i can't quite get my head around
24:26
it feels like i can almost get my head
24:28
around it but i can't quite get my head
24:29
around
24:30
why this um this formula here actually
24:32
is responsible
24:34
for this recursive relation between um
24:36
having a subdivision
24:38
of n quadrilaterals and and
24:40
correspondingly
24:42
the the subdivision of the next bigger
24:45
and gone are two plus two and gone into
24:48
n plus one
24:49
quadrilaterals so adding uh you know
24:52
one more quadrilateral ends up yielding
24:56
this
24:56
multiplicative factor and why that is i
25:00
don't have a uh an explanation
25:03
so already here you see that i'm also at
25:06
a relatively primitive
25:07
state i don't know how to prove this by
25:09
try conjecture in fact i don't even know
25:11
how to
25:12
to deal with this top row okay but
25:14
nevertheless
25:17
we're we're we're laying out you know a
25:19
plan you know so
25:20
somebody else can think about these
25:21
things and maybe you could you could
25:22
figure out some some clever uh
25:24
way of doing things okay so clearly now
25:26
we want to do the same
25:28
kind of thing but more generally along
25:30
the general row
25:31
okay so then we have a kind of a
25:34
satisfying
25:35
um complete picture so along
25:39
the general mth row
25:43
or general row
25:47
which is in the form c m
25:51
and we want to look at n plus 1 as
25:54
something times c
25:58
m n and that's moving along with the m
26:01
th row
26:02
one step at a time okay so let's
26:06
see if we can figure out what the
26:08
something is here
26:09
so c m n plus one so we have to take our
26:12
formula
26:16
for our general entry and replace n with
26:19
n plus one so this n becomes an n plus
26:22
one that introduces a 3 there
26:25
this one here becomes n plus 1 that adds
26:27
2 that makes this
26:28
also a 3. and this n becomes a
26:32
1 plus n okay
26:35
and we want to write that as something
26:38
times
26:40
c m n
26:43
which is same thing as something oops
26:46
something
26:47
times where's our cm in here it is again
26:54
okay and what do we have to put in here
26:56
so it's
27:02
something what should that something be
27:04
okay we have three plus two m plus three
27:06
n factorial
27:07
and over here we have a two m plus three
27:09
n factorial this is completely a kind of
27:12
routine right i don't have to use any
27:14
imagination i just
27:15
expand this thing out as a factorial
27:17
three plus two
27:19
plus 3n that's the top entry the next
27:22
entry will be something similar but
27:24
go down one there'll be another one that
27:27
goes down
27:27
one more yet again and then one more
27:30
down
27:31
we land into this factorial here so that
27:32
takes care of all the
27:34
numerator terms in the denominator we
27:36
have this three plus m plus two n
27:39
factorial and over here we have a one
27:41
plus m plus two n
27:42
so we have to start with a three plus
27:44
two m three plus
27:45
m plus two n and then go down one more
27:49
2 plus m plus 2n we go down one more and
27:52
when we're into this term here
27:55
and finally the m factorials match up
27:58
and the
27:58
n plus one well we need to stick another
28:00
one plus n there
28:02
one plus n
28:07
okay cool and um
28:11
and maybe i'll just summarize this as we
28:12
did before so this equals
28:18
that factor times c m n
28:22
now does this factor simplify at all are
28:24
there any
28:25
cancellations 1 plus n not the factor 3
28:28
plus m plus two
28:29
n three plus m plus two plus two
28:34
i can't see that there's any
28:35
cancellation that looks like
28:37
legitimately a three or degree three
28:40
thing in the
28:41
numerator degree three thing in the
28:43
denominator
28:48
okay so let's summarize so we have
28:51
arrived at the
28:54
general recursions
29:00
uh if we go along down a column
29:05
and this was the one wasn't it
29:07
[Music]
29:09
yes okay that's cm plus one
29:13
so c m plus one
29:16
comma n equals that
29:20
that's going down a row and going down a
29:23
column
29:24
now sorry that first one was going down
29:25
a column and this next one
29:27
is going down across a row
29:31
c m n plus one equals
29:39
that maybe will stick us times in there
29:40
to be consistent how's that look
29:44
the first corresponds
29:49
to going down
29:52
a column which basically means adding
29:56
a triangle in our geometrical
29:58
interpretation
30:00
while the second
30:03
corresponds to
30:07
going across a row
30:11
that's essentially adding a
30:20
quadrilateral
30:22
so here is one way of
30:25
proving the bi-tri conjecture
30:29
is to prove either of these
30:32
okay because we we understand the first
30:36
or the zeroth row and the zeroth column
30:38
of our array
30:39
those are the catalan the foos numbers
30:42
um and we know they correspond to
30:43
subdivisions
30:44
into triangles and quadrilaterals so
30:47
if we know either how to go down a
30:49
general column or we know how to go
30:51
across a general row then that's going
30:55
to prove
30:56
the by try conjecture so either of these
31:01
would prove
31:05
conjecture okay
31:08
so a fabulous
31:11
to do isn't it
31:16
now you can think geometrically you can
31:22
you know start with the simpler columns
31:24
like
31:25
start with the first column or the first
31:26
row
31:28
and see if you can figure out you know
31:29
what is the meaning of these factors
31:33
obviously this one looks simpler because
31:34
it's only quadratic so that's all the
31:36
natural ones to start with but it's kind
31:38
of a nice challenge to try to see if you
31:40
can figure out this one as well
31:41
okay so i think these are great
31:44
great you know activities and don't
31:48
expect that you're going to do this in
31:49
an hour or two okay
31:51
this could easily take uh you know you
31:53
could easily spend some months on this i
31:55
have no idea okay but maybe some clever
31:57
person
31:58
can do it quickly but i don't know
32:00
anyway
32:01
quite exciting and uh and i think this
32:04
you know shows
32:04
us the the power of harnessing the
32:08
the algebra to the geometry