Try this beautiful Recursion Problem based on Binary Tree appeared in IOQM 2022 Part B, Problem 3.
For a positive integer $N$, let $T(N)$
denote the number of arrangements
of the integers $\\$ $1,2, \ldots, N$
into a sequence $a_{1}, a_{2}, \ldots, a_{N}$
such that
$a_{i}>a_{2 i}$ for all $i, 1 \leq i<2 i \leq N \\$
and
$a_{i}>a_{2 i+1}$,
for all $i, 1 \leq i<2 i+1 \leq N$.
For example, $T(3)$ is 2 , since
the possible
arrangements are 321 and 312 .
(a) Find $T(7)$.
(b) If $K$ is the largest non-negative
integer
so that $2^{K}$ divides $T\left(2^{n}-1\right)$,
show that $\\K=$ $2^{n}-n-1$.
(c) Find the largest non-negative
integer
$K$ so that
$2^{K}$ divides $T\left(2^{n}+1\right)$.
Binary Tree
Recursion Relation
Induction
Problem Solving Strategies by Arthur Engel
IOQM 2022
$ (i) 80 $
$ (iii)$ The highest power of $2$ dividing $T\left(2^{n}+1\right)$ is $ 2^{n}-1 $
Create a Binary Tree with nodes using the given numbers as the following rule:
At each node the root is greater than the child node
Observe a bijection between the these nodes and every possible valid arrangements
Observe that the maximum number will be the root. Now try to find how the subsequent nodes will be formed.
Leave the maximum number for the root. Then we would have \(2^{n}-2\) numbers.
Now they can be grouped into 2 groups of \(2^{n-1}-1\) numbers each.
Try to build a recursion using \(T(N)\).
Then observe
\[
2^{n-2}
{{2^{n}}\choose {2^{n-1}}}
=(2^{n}-1){{2^{n}-2}\choose{2^{n-1}-1}}
\]
Then find the highest power of \(2\) which divides\({{2^n}\choose {2^{n-1}}}.\)
Try to solve this similarly as the second part.
Then try to build a recursive relation of the highest power of 2 dividing $T(N)$ an solve it
Try this beautiful Recursion Problem based on Binary Tree appeared in IOQM 2022 Part B, Problem 3.
For a positive integer $N$, let $T(N)$
denote the number of arrangements
of the integers $\\$ $1,2, \ldots, N$
into a sequence $a_{1}, a_{2}, \ldots, a_{N}$
such that
$a_{i}>a_{2 i}$ for all $i, 1 \leq i<2 i \leq N \\$
and
$a_{i}>a_{2 i+1}$,
for all $i, 1 \leq i<2 i+1 \leq N$.
For example, $T(3)$ is 2 , since
the possible
arrangements are 321 and 312 .
(a) Find $T(7)$.
(b) If $K$ is the largest non-negative
integer
so that $2^{K}$ divides $T\left(2^{n}-1\right)$,
show that $\\K=$ $2^{n}-n-1$.
(c) Find the largest non-negative
integer
$K$ so that
$2^{K}$ divides $T\left(2^{n}+1\right)$.
Binary Tree
Recursion Relation
Induction
Problem Solving Strategies by Arthur Engel
IOQM 2022
$ (i) 80 $
$ (iii)$ The highest power of $2$ dividing $T\left(2^{n}+1\right)$ is $ 2^{n}-1 $
Create a Binary Tree with nodes using the given numbers as the following rule:
At each node the root is greater than the child node
Observe a bijection between the these nodes and every possible valid arrangements
Observe that the maximum number will be the root. Now try to find how the subsequent nodes will be formed.
Leave the maximum number for the root. Then we would have \(2^{n}-2\) numbers.
Now they can be grouped into 2 groups of \(2^{n-1}-1\) numbers each.
Try to build a recursion using \(T(N)\).
Then observe
\[
2^{n-2}
{{2^{n}}\choose {2^{n-1}}}
=(2^{n}-1){{2^{n}-2}\choose{2^{n-1}-1}}
\]
Then find the highest power of \(2\) which divides\({{2^n}\choose {2^{n-1}}}.\)
Try to solve this similarly as the second part.
Then try to build a recursive relation of the highest power of 2 dividing $T(N)$ an solve it
