Nondecreasing subsequences of t-sequences (Q908917)

A sequence of nonnegative integers is called a t-sequence if consecutive elements differ by no more than 1. The integer g(m,n) is the smallest k such that every t-sequence of length k starting with m contains a nondecreasing subsequence of length n. The author demonstrates, with elementary arguments, that \(g(m,n)=n(n-1)/2+m(n-1)+1.\) This function is related to the longest path in a tree construction algorithm used to solve the boundedness problem for one-dimensional vector addition systems with states.