I recently saw a very nice problem. It's a problem on Continuous distribution but I recognized it's one of those problems where the reasoning can be applied exactly to the discrete case too. So here it is.
Consider the following sum.
$T(n)=\displaystyle\sum_{j_1=1}^n\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1$
One interpretation of the above sum can be as follows: The sum counts the number of $k$-tuples of positive integers such that each integer in the tuple is less than or equal $n$ and the sum of any two consecutive elements in the tuple in less than or equal to $n$ as well.
To find this sum, let's modify the notation a bit. Let
$T_k(m)=\displaystyle\sum_{j_1=1}^{n-m}\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1$
So we are solving for $T_k(0)$ given $n$. Now we take advantage of the iterative structure of the sum to write it as,
$T_k(m)=\displaystyle\sum_{j=1}^{n-m}T_{k-1}(j)$
with $T_0(m)=1$. This may be a little confusing but a moment of thought clears it up easily. Now this renders itself to the idea of generating functions. We define,
$f(z,m)=\displaystyle\sum_{j=0}^\infty T_j(m)z^j$
Let's do some algebraic manipulations in the above sum.
$\begin{align}
f(z,m)&=1+z\sum_{j=1}^\infty T_j(m)z^{j-1}\\
&=1+z\sum_{j=1}^\infty z^{j-1} \sum_{i=1}^{n-m}T_{j-1}(i)\\
&=1+z\sum_{i=1}^{n-m} \sum_{j=1}^\infty T_{j-1}(i)z^{j-1}\\
&=1+z\sum_{i=1}^{n-m} f(z,i)\\
\end{align}$
We can infer that
$(1):$ $f(z,h+1)-f(z,h)=-z f(z,n-h)$
$(2):$ $f(z,h+2)-2f(z,h+1)+f(z,h)=-z (f(z,n-h-1)-f(z,n-h))$
$(3):$ $f(z,n)=1$
$(4):$ Using $h=0$ in $(1)$, we have $f(z,1)-f(z,0)=-z$ (using $(3)$)
Using $h=n-m-1$ in $(1)$, we have $f(z,n-m)-f(z,n-m-1)=-z f(z,m+1)$. Substituting this in $(2)$, we finally arrive at,
$f(z,m+2)-2f(z,m+1)+f(z,m)=-z^2f(z,m+1)$
This is a simple difference equation of the second order. The characteristic equation of this is,
$x^2+(z^2-2)x+1=0$ with roots $z_{+,-}=\displaystyle\frac{1}{2}(2-z^2\pm z\sqrt{z^2-4})$
Therefore, $f(z,m)=c_1 z_+^m+c_2 z_-^m$. Note that our point of interest $f(z,0)=c_1+c_2$
We use $(3)$ and $(4)$ to solve for these constants. Finally,
$T_k(0)=[z^k]f(z,0)=[z^k]\displaystyle\frac{z_+^n-z_+^{-n}+\sqrt{z^2-4}}{\frac{z}{2}(z_+^n-z_+^{-n})+\frac{\sqrt{z^2-4}}{2}(z_+^n+z_+^{-n})}$
Honestly, the entire idea so far has been adapted to the discrete case from the original source. Moreover, the given expression looks complicated. It seems we can simplify this and somehow get rid of the radical terms but I was not able to.
But I did all these because, first of all, it was fun and second, I was able to notice something very nice which would be my original contribution to this post.
Let $f_j(z)=z+\displaystyle\frac{1}{f_{j-1}(-z)}$ with $f_0(z)=1$. Then $T_k(0)=[z^k]f_n(z)$. That is,
$\displaystyle\sum_{j_1=1}^n\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1=[z^k] \text{ }[z;-z,z,-z,\cdots,(-1)^{n-1}z,1]$
in continued fraction notation. Note that there are $n$ $z$'s on the RHS and the sign alternates with every iterate.
I really liked how an iterated sums occur on one side, a continued fraction on the other and levels on both sides $k$ and $n$ in a twisted way. Not only does this make the sum compact (also freeing it of any radicals), it also makes it easier to program. I used this idea to make a Python program for different $k$.
Yeah, my original idea was very small compared to the length of the post but it was great learning experience for me going through a problem in both continuous and discrete cases side-by-side, understanding how each steps transpires in both of them. Hope you enjoyed this.
Until then
Yours Aye
Me.
Consider the following sum.
$T(n)=\displaystyle\sum_{j_1=1}^n\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1$
One interpretation of the above sum can be as follows: The sum counts the number of $k$-tuples of positive integers such that each integer in the tuple is less than or equal $n$ and the sum of any two consecutive elements in the tuple in less than or equal to $n$ as well.
To find this sum, let's modify the notation a bit. Let
$T_k(m)=\displaystyle\sum_{j_1=1}^{n-m}\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1$
So we are solving for $T_k(0)$ given $n$. Now we take advantage of the iterative structure of the sum to write it as,
$T_k(m)=\displaystyle\sum_{j=1}^{n-m}T_{k-1}(j)$
with $T_0(m)=1$. This may be a little confusing but a moment of thought clears it up easily. Now this renders itself to the idea of generating functions. We define,
$f(z,m)=\displaystyle\sum_{j=0}^\infty T_j(m)z^j$
Let's do some algebraic manipulations in the above sum.
$\begin{align}
f(z,m)&=1+z\sum_{j=1}^\infty T_j(m)z^{j-1}\\
&=1+z\sum_{j=1}^\infty z^{j-1} \sum_{i=1}^{n-m}T_{j-1}(i)\\
&=1+z\sum_{i=1}^{n-m} \sum_{j=1}^\infty T_{j-1}(i)z^{j-1}\\
&=1+z\sum_{i=1}^{n-m} f(z,i)\\
\end{align}$
We can infer that
$(1):$ $f(z,h+1)-f(z,h)=-z f(z,n-h)$
$(2):$ $f(z,h+2)-2f(z,h+1)+f(z,h)=-z (f(z,n-h-1)-f(z,n-h))$
$(3):$ $f(z,n)=1$
$(4):$ Using $h=0$ in $(1)$, we have $f(z,1)-f(z,0)=-z$ (using $(3)$)
Using $h=n-m-1$ in $(1)$, we have $f(z,n-m)-f(z,n-m-1)=-z f(z,m+1)$. Substituting this in $(2)$, we finally arrive at,
$f(z,m+2)-2f(z,m+1)+f(z,m)=-z^2f(z,m+1)$
This is a simple difference equation of the second order. The characteristic equation of this is,
$x^2+(z^2-2)x+1=0$ with roots $z_{+,-}=\displaystyle\frac{1}{2}(2-z^2\pm z\sqrt{z^2-4})$
Therefore, $f(z,m)=c_1 z_+^m+c_2 z_-^m$. Note that our point of interest $f(z,0)=c_1+c_2$
We use $(3)$ and $(4)$ to solve for these constants. Finally,
$T_k(0)=[z^k]f(z,0)=[z^k]\displaystyle\frac{z_+^n-z_+^{-n}+\sqrt{z^2-4}}{\frac{z}{2}(z_+^n-z_+^{-n})+\frac{\sqrt{z^2-4}}{2}(z_+^n+z_+^{-n})}$
Honestly, the entire idea so far has been adapted to the discrete case from the original source. Moreover, the given expression looks complicated. It seems we can simplify this and somehow get rid of the radical terms but I was not able to.
But I did all these because, first of all, it was fun and second, I was able to notice something very nice which would be my original contribution to this post.
Let $f_j(z)=z+\displaystyle\frac{1}{f_{j-1}(-z)}$ with $f_0(z)=1$. Then $T_k(0)=[z^k]f_n(z)$. That is,
$\displaystyle\sum_{j_1=1}^n\sum_{j_2=1}^{n-j_1}\sum_{j_3=1}^{n-j_2}\cdots\sum_{j_k=1}^{n-j_{k-1}}1=[z^k] \text{ }[z;-z,z,-z,\cdots,(-1)^{n-1}z,1]$
in continued fraction notation. Note that there are $n$ $z$'s on the RHS and the sign alternates with every iterate.
I really liked how an iterated sums occur on one side, a continued fraction on the other and levels on both sides $k$ and $n$ in a twisted way. Not only does this make the sum compact (also freeing it of any radicals), it also makes it easier to program. I used this idea to make a Python program for different $k$.
Yeah, my original idea was very small compared to the length of the post but it was great learning experience for me going through a problem in both continuous and discrete cases side-by-side, understanding how each steps transpires in both of them. Hope you enjoyed this.
Until then
Yours Aye
Me.
No comments:
Post a Comment