Math Help -> Puzzles -> Nondecreasing integer sequence 2 -> Answer 

Let a₁,a₂,...,a₂₀₀₅ be a nondecreasing sequence of positive integers, with t defined as t=a₂₀₀₅.
Let b_n be the smallest index, m, for which a_m ≥ n.
In terms of t, what is the smallest possible value of the sum a₁+a₂+...+a₂₀₀₅+b₁+b₂+...+b_t ?

Solution:

First, some definitions:
a₁,a₂,...,a_p is a nondecreasing sequence of positive integers,
t is defined as t=a_p,
b_n is the smallest index, m, for which a_m ≥ n,
the sum S_p,t is defined by S_p,t=a₁+a₂+...+a_p+b₁+b₂+...+b_t;

I will prove by induction that S_p,t=(p+1)(t), regardless of the values of a₁ through a_p-1.

Proof:

The statement is true when p=1, because a₁=t, and b₁,b₂,...,b_t are all equal to 1.
So the sum of the a's is t, and the sum of the b's is also t, so S_1,t=2t.

Then, in the induction step, we assume S_p,t=(p+1)(t), and introduce a new element a_p+1=t+k, where k is a nonnegative integer.

Each of the b's in the range b_t+1 through b_t+k, of which there are zero or more, are equal to p+1, so their sum is (p+1)(k)

S_p+1,t+k=S_p,t+a_p+1+b_t+1+b_t+2+...+b_t+k
S_p+1,t+k=(p+1)(t)+(t+k)+(p+1)(k)
S_p+1,t+k=(p+2)(t+k),