Information Technology Reference
In-Depth Information
Therefore, the following equation holds (
n
>
3):
UB
(
n
)=
UB
(
n
−
1
)(
2
(
n
−
1
)
−
3
)
whence, for
n
>
3:
UB
(
n
)=
3
·
5
·...·
(
2
(
n
−
1
)
−
3
)=
3
·
5
·...·
(
2
n
−
5
)
.
Thus, the number
UB
(
n
)
given above, for
n
>
2, can be concisely expressed by
(denoting
n
·
(
n
−
2
)
·
(
n
−
4
)
...·
3by
n
!!):
UB
(
n
)=(
2
n
−
5
)
!!
Therefore, from Proposition 7.18, we get
BT
(
n
)=(
2
n
−
3
)
!!, which concludes the
proof.