Proving that, if $f(k)=\prod_{i=1}^ka_i+\sum_{b=1}^{k-1}(1-a_{k-b})\prod_{i=1}^ba_{k-b+i}$, then $f(k+1)=f(k)\cdot a_{k+1}+(1 - a_k)a_{k+1}$

Question

Given that $$f(k) = \prod_{i=1}^k a_i + \sum_{b=1}^{k-1} (1-a_{k-b}) \prod_{i=1}^b a_{k-b+i}$$ for all $k$ where $(a_1, a_2, a_3, \ldots )$ are random constants, prove that: $$f(k+1) = f(k) \cdot a_{k+1} + (1 - a_k)a_{k+1}$$

So far, my current work is:

$$f(k+1) = \prod_{i=1}^{k+1} a_i + \sum_{b=1}^{k} (1-a_{k-b+1}) \prod_{i=1}^b a_{k-b+i+1} = a_{k+1}\prod_{i=1}^{k+1} a_i + \sum_{b=1}^{k} (1-a_{k-b+1}) \prod_{i=1}^b a_{k-b+i+1}.$$

So, we have to show that: $$a_{k+1}\prod_{i=1}^{k+1} a_i + \sum_{b=1}^{k} (1-a_{k-b+1}) \prod_{i=1}^b a_{k-b+i+1} = a_{k+1}\prod_{i=1}^{k+1} a_i + a_{k+1}\sum_{b=1}^{k-1} (1-a_{k-b}) \prod_{i=1}^b a_{k-b+i} + (1-a_k)(a_{k+1}).$$

The $a_{k+1}\prod_{i=1}^{k+1} a_i$ cancel out on both sides, leaving us to prove: $$\sum_{b=1}^{k} (1-a_{k-b+1}) \prod_{i=1}^b a_{k-b+i+1} = a_{k+1}\sum_{b=1}^{k-1} (1-a_{k-b}) \prod_{i=1}^b a_{k-b+i} + (1-a_k)(a_{k+1}).$$

Turning the max value of $i$ on the first summation to $k-1$ and changing the second series of products a bit to match the first one gives:

\begin{align} \sum_{b=1}^{k-1} (1-a_{k-b+1}) \prod_{i=1}^b a_{k-b+i+1} + (1-a_1)\prod_{i=1}^k a_{k-b+i+1} = &\\ a_{k+1} \sum_{b=1}^{k-1} \left( (1-a_{k-b}) \prod_{i=1}^b a_{k-b+i+1} \cdot \frac{a_{k-b+1}}{a_{k+1}}\right) + (1-a_k)(a_{k+1}). \end{align}

We can cancel out the $a_{k+1}$ terms on the RHS, leaving us to prove: $$\sum_{b=1}^{k-1} (1-a_{k-b+1}) \prod_{i=1}^b a_{k-b+i+1} + (1-a_1)\prod_{i=1}^k a_{k-b+i+1} = \sum_{b=1}^{k-1} \left( (1-a_{k-b}) a_{k-b+1} \prod_{i=1}^b a_{k-b+i+1}\right) + (1-a_k)(a_{k+1}).$$

However, I don't know how to continue on from here. Any help would be greatly appreciated.

Answer 1

We can considerably simplify $f(k)$ which makes the proof easy.

We obtain \begin{align*} \color{blue}{f(k)}&=\prod_{i=1}^k a_i+\sum_{b=1}^{k-1}\left(1-a_{k-b}\right)\prod_{i=1}^b a_{k-b+i}\\ &=\prod_{i=1}^k a_i+\sum_{b=1}^{k-1}\left(1-a_{b}\right)\prod_{i=1}^{k-b} a_{b+i}\tag{1}\\ &=\prod_{i=1}^k a_i+\sum_{b=1}^{k-1}\prod_{i=1}^{k-b} a_{b+i}-\sum_{b=1}^{k-1}a_b\prod_{i=1}^{k-b} a_{b+i}\\ &=\prod_{i=1}^k a_i+\sum_{b=2}^{k}\prod_{i=1}^{k-b+1} a_{b-1+i}-\sum_{b=1}^{k-1}\prod_{i=0}^{k-b} a_{b+i}\tag{2}\\ &=\prod_{i=1}^k a_i+\sum_{b=2}^{k}\prod_{i=0}^{k-b} a_{b+i}-\sum_{b=1}^{k-1}\prod_{i=0}^{k-b} a_{b+i}\tag{3}\\ &=\prod_{i=1}^k a_i+a_k-\prod_{i=0}^{k-1} a_{i+1}\tag{4}\\ &=\prod_{i=1}^k a_i+a_k-\prod_{i=1}^{k} a_{i}\tag{5}\\ &\,\,\color{blue}{=a_k}\tag{6} \end{align*}

Comment:

• In (1) we change the order of summation of the sum $b\to k-b$.

• In (2) we shift the index of $b$ by one in the left sum and merge the factor $a_b$ into the product of the right sum.

• In (3) we shift the index of the product in the left sum by one and observe the sums are telescoping.

• In (4) we do the telescoping.

• In (5) we shift the index of the right-hand product and simplify in the next line.

With $f(k)=a_k$ the proof is simple, since we have \begin{align*} \color{blue}{f(k) a_{k+1} + (1 - a_k)a_{k+1}}&= a_ka_{k+1}+(1-a_k)a_{k+1}=a_{k+1}\\ &\color{blue}{=f(k+1)} \end{align*} and the claim follows.