Obtaining expression for recursive sequence

Question

Can someone suggest how to obtain an expression for $S[i]$ given that S[0] = 0,

$S[i]=S[i-1]*(1-\gamma_i)^2 + \gamma_i^2$ where $\gamma_i = \frac{g+1}{g+i}$

EDIT: $g>0$ and $g$ can be assumed to be a natural number.

An exact expression or a lower bound would be helpful.

Thanks!

Answer 1

I was able to determine a formula for this based off of looking at the first few elements of the sequence.

I have that $$s_i=\gamma_i^2(\sum_{n=1}^{i-1}(\prod _{k=n}^{i-1}\frac{k^2}{(g+k)^2})+1).$$

Now let’s look at bounding it from below. From your hunch that there is a $c$ such that $(g+i)s_i>c$, we proceed by finding which $c$ might give us an induction argument.

Suppose $(g+i)s_i>c$ for $i>0$. Then $$(g+i+1)s_{i+1}=\frac{i^2 s_i}{(g+i+1)}+\frac{(g+1)^2}{g+i+1} > \frac{i^2 c+(g+1)^2}{(g+i+1)^2}.$$

If we find a $c$ such that the final expression of the previous paragraph is greater than $c$ for all $i>0$, then we have the desired result. After some algebra and working backwards, it can be shown that any $c<(g+1)/2$ satisfies it. Following through with the induction argument, we can see that the base case ($i=1$) is satisfied since $s_1>1/2$.

Answer 2

For a sequence $(S_i)_{i\in\mathbb N}$ generated as $S_i=a_iS_{i-1}+b_i$ with $a_i,b_i\in\mathbb R$, by recursively expanding once ore twice you can easily obtain a general formula. $$\begin{align} S_i {}={} & a_iS_{i-1}+b_i \\ {}={} & a_i(a_{i-1}S_{i-2}+b_{i-1})+b_i \\ & {}\vdots{} \\ {}={} & a_ia_{i-1}\cdots a_1 S_0 {}+{} b_i+a_ib_{i-1}+a_ia_{i-1}b_{i-2}+\ldots+ a_ia_{i-2}\cdots a_2b_1 \\ {}={} & S_0\prod_{j=1}^ia_j {}+{} \sum_{j=1}^ib_j\prod_{k=j+1}^ia_k. \end{align}$$ In your case $S_0=0$, hence the first term above vanishes. What you need is a way to compute the remaining products and sums.

Since $ a_k {}={} \left(1-\frac{g+1}{g+k}\right)^2 {}={} \frac{(k-1)^2}{(g+k)^2} $ and $b_j=\frac{(g+1)^2}{(g+j)^2}$, you have $$\begin{align} \color{red}{b_j}\prod_{k=j+1}^ia_k {}={} & \color{red}{\frac{(g+1)^2}{(g+j)^2}} \,\, \frac{j^2}{(g+j+1)^2} \frac{(j+1)^2}{(g+j+2)^2} {}\cdots{} \frac{(i-2)^2}{(g+i-1)^2} \frac{(i-1)^2}{(g+i)^2} \\ {}={} & \color{red}{\frac{(g+1)^2}{(g+j)^2}} \,\, \frac{(i-1)!^2}{(j-1)!^2} \frac{(g+j)!^2}{(g+i)!^2} \\ {}={} & (g+1)^2 \frac{(i-1)!^2}{(j-1)!^2} \frac{(g+j-1)!^2}{(g+i)!^2}, \end{align}$$ where for simplicity $g$ was assumed natural. The general case can easily be adapted by redefining the factorial accordingly (that is, $g!:=g$ and $(x+1)!:=(x+1)x!$, defined for $x\in g+\mathbb N$).

Therefore, $$\begin{align} S_i {}={} & \frac{(g+1)^2(i-1)!^2}{(g+i)!^2} \sum_{j=0}^{i-1} \frac{(g+j)!^2}{j!^2} \\ \tag{1} \mbox{(EDIT)}\quad {}={} & \frac{1}{\binom{g+i}{i-1}^2} \sum_{j=0}^{i-1} \binom{g+j}{j}^2. \end{align}$$ Now, in order to obtain a lower bound, notice that $$ \binom{g+j}{j} {}={} \binom{g+j-1}{j-1}\frac{g+j}{j} {}\geq{} \binom{g+j-1}{j-1}\left(\textstyle 1+\frac{g}{i-1}\right) \quad \mbox{for }j\leq i-1 $$ therefore, $$ \binom{g+j}{j}^2 {}\geq{} \binom{g}{0}^2\left(\textstyle 1+\frac{g}{i-1}\right)^{2j} {}={} \left(\textstyle 1+\frac{g}{i-1}\right)^{2j}, $$ and plugging this into (1) yields $$\begin{align} S_i {}\geq{} & \frac{1}{\binom{g+i}{i-1}^2} \sum_{j=0}^{i-1} \left(\textstyle 1+\frac{g}{i-1}\right)^{2j} {}={} \frac{1}{\binom{g+i}{i-1}^2} \frac{(1+\frac{g}{i-1})^{2i}-1}{(1+\frac{g}{i-1})^2-1}. \end{align}$$