We have a set of jobs $J_i = (a_i, b_i)$ where all the $a_i,b_i \ge 0$. We want to find the permutation $\pi$ which minimises $$\max_j \left\{ b_{\pi(j)} + \sum_{k \le j}a_{\pi(k)} \right\}$$
Suppose we have proven that for all job sets $X$ of size no greater than $n$ the permutation which sorts the jobs by descending $b_i$ breaking ties by descending $a_i$ is an optimal solution (bearing in mind that there may be more than one optimal solution). (Call this ordering doubly-reverse-lexicographical because it sorts in descending order starting from the right).
Consider a job set $Y$ of size $n+1$ whose "worst" job is $J_{n+1}$, and suppose that there is no optimal solution in which this job comes first. Of the optimal solutions select one which puts $J_{n+1}$ as early as possible, in position $j^* = \pi^{-1}(n+1) > 0$. Now, which $j$ maximises the expression above (i.e. which job finishes last)?
Given that $b_{\pi(j^*)}$ is maximal by construction and the sum is non-decreasing the maximising $j$ must be $\ge j^*$. Also, if the maximising $j > j^*$ we can move $J_{n+1}$ to the start without affecting the optimality, so by contradiction that's impossible. We're forced to conclude that $J_{n+1}$ is the job which finishes last.
Now consider what happens if we swap it with the job before it. Call that job $J_p$ for previous. $J_p$'s finishing time increases from $b_p + \sum_{k < j^*}a_{\pi(k)}$ to $b_p + \sum_{k \le j^*}a_{\pi(k)} \le b_{n+1} + \sum_{k \le j^*}a_{\pi(k)}$ and $J_{n+1}$'s finishing time decreases from $b_{n+1} + \sum_{k \le j^*}a_{\pi(k)}$ to $b_{n+1} + \sum_{k \le j^* \wedge k \ne j^*-1}a_{\pi(k)}$ so we have a contradiction with this being an optimal solution which puts $J_{n+1}$ as early as possible.
We've now proven that there is an optimal solution for $Y$ in which $J_{n+1}$ comes first. Either some of these optimal solutions allow for the rest of the jobs to be ordered non-optimally because the worst job is so bad that it doesn't matter – in which case putting them in an optimal ordering will give an optimal ordering – or the rest of the jobs must be optimally ordered to get an optimal ordering. In either case we can apply our strong inductive presupposition to say that there is an optimal ordering which is doubly-reverse-lexicographical.
The base case of only one job is trivial.
You concern makes sense.Moreover I am sure that in general you are correct and
and optimal on 1 period strategy does not have to be optimal on all period.
But for this specific example it seems for me it is indeed true.
It seems for me that your calculations of the return for the second period are wrong. At least I don't understand how do you get these numbers.
So let's calculate from the beginning.
Let $E_n(C,X_{n,n+1...})$ be an expected return of your invested return since period $n$ to the end (n=3) with given capital $C$ and the strategy $X$.$X$ is the sequence of strategies. Let $E_n^1(C,X)$ be 1 period expected return.
Let $B_n(X)$ be maximum of such return.Let $E_n^1(C,X)$ be 1 period expected return. (In both return we include the rest of capital if $C>5000$). Also let
$R^1_n(C,X)$ be realized 1 period return.
Then
Obviously
$$
B_n(C)=\max_{X} E_n^1(C,X)+E(B_{n+1}(R_n^1(C,X)))
$$
Let's start from $B_3$ (you almost finihes this part)
So
$$
B_3(C)=\max((C-5000,0)+\min(C,5000)*7/5;
$$
Assume now that $C\ge 5000$ and $D=C-5000$.
Then $B_3(C)=D+7000$
Assume now that $C<5000$. Then
$B_3(C)=C*7/5$;
However $C$ is random on the 3d period. It depends on the previous capital and the chosen strategy at the previos period.
Assume that at the begining of the previous period we have capital $C_2$.
Then
$$
R^1_2(C_2,A)=(\max(C_2-5000,0)+2\min(C_2,5000) \text { with } P=0.7\\
R^1_2(C_2,A)=\max(C_2-5000,0) \text { with }P=0.3 \\
R^1_2(C_2,B)=(\max(C_2-5000,0)+2\min(C_2,5000) \text { with } P=0.1\\
R^1_2(C_2,B)=\max(C_2-5000,0) +\min(C_2,5000)=C_2\text { with }P=0.9 \
$$
Thus
$$
E (B_3(R^1_2(C_2,A)))=0.7\cdot B_3((\max(C_2-5000,0)+2\cdot\min(C_2,5000))+0.3B_3(\max(C_2-5000,0))\\
E (B_3(R^1_2(C_2,B)))=0.1\cdot B_3((\max(C_2-5000,0)+2\cdot\min(C_2,5000))+0.9(B_3(C_2))
$$
The difference
$$
E (B_3(R^1_2(C_2,A)))-E (B_3(R^1_2(C_2,B)))
$$
It is not so simple calculation but checking different intervals for $C_2$: $[0,2500],[2500,5000],[5000,10000],[10000,\infty)$ one can prove that it always positive. Thus
and
since $B_3(C)$ is strictly monotonic in $C$ then to get $B_2$ we have to maximize $E_n^1(C,X)$ ONLY. Thus
$$
B_2(C)=(C-5000,0)+\min(C,5000)*7/5+0.7 B_3(\max((C-5000,0)+2\min(C,5000))+0.3 B_3(\max((C-5000,0)
$$
Notice now that since $C_1=5000$ we can easily can calculate $B_2$ for all 3 possible outcomes from the period $1$ - $0,5000,1000$.
$$
B_2(0)=0; B_2(5000)=7000+0.7(5000+7000)=15400; B_2(10000)=5000+7000+0.7(5000+10000)+0.3 7000=24600;
$$
Thus
$$
0.7 B_2(10000)+0.3 B_2(0)=0.7\cdot 24600=17220\\
0.1 B_2(10000)+0.9 B_2(5000)=0.1\cdot 24600+0.9\cdot 15400=16320
$$
So again $A$ is optimal on the first period too. And finally
$$
B_1(5000)=7000+0.7 B_2(10000)+0.3 B_2(0)=24220;
$$
REMARK
In general, however for me is absolutely not obvious that the optimal strategy on 1 period should be optimal on all period. Moreover, I am sure I can find contr examples when it is better to switch the strategies.
Best Answer
Let's compute the number of inner loop iterations: $$\sum_{\ell = 2}^n\sum_{i = 1}^{n - \ell + 1}\sum_{k = i}^{i + \ell - 2} 1 = \sum_{\ell = 2}^n\sum_{i = 1}^{n - \ell + 1}(\ell - 1) = \sum_{\ell = 2}^n (n - \ell + 1)(\ell - 1)\\ = \sum_{\ell = 1}^n (n - \ell + 1)(\ell - 1) = \sum_{\ell = 1}^n (n\ell - \ell^2 - n + 2\ell - 1)\\ = \frac{n^2(n + 1)}{2} - \frac{n(n + 1)(2n + 1)}{6} - n^2 + n(n - 1) - n \sim \frac{n^3}{6} = \Omega(n^3).$$
Another approach is the following. You choose all triples $(i, k, j)$ such that $1 \le i \le k < j \le n$ and make some work for each triple. The number of such triples is the same as the number of triples $(i', k, j)$ such that $0 \le i' < k < j \le n$. It is the same as choosing subset of 3 elements from $\{\,0, 1, \ldots, n\,\}$. There are $\binom{n + 1}{3} \sim \frac{n^3}{6} = \Omega(n^3)$ of them.