Solving a discrete functional equation: $a_1=0$, $a_{p+1}=n$ and $\sum_{i=a_{k+1}}^{a_{k+2}}n-(i+1)=\sum_{i=a_k}^{a_{k+1}}n-(i+1)$

Question

I was to solve the discrete functional equation (considering $ a _ k $ is a discrete function) $$ f [ a _ { k + 1 } ] - f [ a _ k ] = 0 $$ where $$ f [ a _ k ] = \sum _ { i = a _ k } ^ { a _ { k + 1 } } n - ( i + 1 ) $$ with boundary conditions $$ \begin {cases} a _ 1 & = 0 \\ a _ { p + 1 } & = n \end {cases} $$ where $ n > 1 $, $ p > 0 $ and $ k = 1 , 2 , 3 , \dots , p $.

The sum can be calculated, and I've arrived at the following non-linear recurrence relation: $$ ( 1 - 2 n ) a _ k + ( 4 n - 2 ) a _ { k + 1 } + a _ { k + 2 } ( a _ { k + 2 } - 2 n + 1 ) + a _ k ^ 2 = 2 a _ { k + 1 } ^ 2 $$

After trying several approaches, I desperately tried brute force, calculating numerical results for different values of the parameters, and with some effort, I found this simple equation: $$ a _ k = \frac 1 { 2 p } \left( - p + 2 p ( n + 1 ) - \sqrt{ p ^ 2 + 4 p ( p + 1 - k ) ( n + 1 ) n } \right) $$ which:

1. agrees with the boundary conditions;
2. when substituted in the recurrence relation, gives a true statement;

which I believe is enough to prove that this is a solution of the problem.

what I'm asking is whether there is any method for solving this problem that can lead me to the same result without having to make this "ansatz". The solution looks very simple, suggesting a possible analytical method for solving the recurrence relation (the expression seems to be the solution of a certain second order algebraic equation).

Answer 1

Let's rephrase your question as follows:*

Consider a positive natural number $ p $ and a real number $ n $ greater than $ 1 $. Suppose that there is a finite increasing sequence $ ( a _ k ) _ { k = 0 } ^ p $ of nonnegative real numbers such that $ a _ 0 = 0 $, $ a _ p = n $, and for any natural number $ k $ less than $ p - 1 $, $$ f ( a _ { k + 1 } , a _ { k + 2 } ) - f ( a _ k , a _ { k + 1 } ) = 0 \text , \tag 0 \label 0 $$ where $ f $ is a bivariate real functions with $$ f ( u , v ) = ( v - u ) ( n + 1 ) - \frac { v ( v + 1 ) - u ( u + 1 ) } 2 \text . \tag 1 \label 1 $$ Find an explicit formula for $ a _ k $ in terms of elementary functions, with $ p $ and $ n $ as parameters.

To make things look simpler, first define the real function $ g $ with $ g ( w ) = w ( 2 n - w + 1 ) $ for all real numbers $ w $. Then define the finite sequence $ ( b _ k ) _ { k = 0 } ^ p $ of real numbers with $ b _ k = g ( a _ k ) $ for all natural numbers $ k $ no more than $ p $. Now, you can rewrite the "boundary conditions" as $ b _ 0 = 0 $ and $ b _ p = n ( n + 1 ) $, and the recurrence relation \eqref{0} as $$ b _ { k + 2 } - b _ { k + 1 } = b _ { k + 1 } - b _ k \tag 2 \label 2 $$ for any natural number $ k $ less than $ p - 1 $. \eqref{2} means that $ ( b _ k ) _ { k = 0 } ^ p $ is in fact an arithmetic progression, and thus we must have $ b _ k = b _ 0 + k d $ for all natural numbers $ k $ no more than $ p $, where $ d $ is the common difference of the progression. As $ b _ 0 = 0 $ and $ b _ p = n ( n + 1 ) $, we get $ b _ k = \frac { k n ( n + 1 ) } { p } $ for all natural numbers $ k $ no more than $ p $. By definition of $ ( b _ k ) _ { k = 0 } ^ p $, we have $ a _ k ^ 2 - ( 2 n + 1 ) a _ k + \frac { k n ( n - 1 ) } p = 0 $, which shows that $$ a _ k = \frac 1 2 \left( 2 n + 1 \pm \sqrt { ( 2 n + 1 ) ^ 2 - \frac 4 p k n ( n + 1 ) } \right) \text . $$ As $ a _ p = n $, the "$ \pm $" in the above formula must be "$ - $" when $ k = p $. Since the sequence is assumed to be increasing, it follows that this must be true for all natural numbers $ k $ no more than $ p $, which means $$ a _ k = \frac 1 2 \left( 2 n + 1 - \sqrt { ( 2 n + 1 ) ^ 2 - \frac 4 p k n ( n + 1 ) } \right) \text . \tag 3 \label 3 $$

Note:

As you expected, $ a _ k $ is the root of the quadratic polynomial $$ p _ k ( x ) = x ^ 2 - ( 2 n + 1 ) x + b _ k \text . $$ This can be directly derived from the definition of $ g $ and $ b _ k = g ( a _ k ) $. Aside from simplifying the formula you had for $ a _ k $ and finding what $ p _ k $ should look like, an idea for getting a quadratic polynomial which has $ a _ k $ as a root is to look at \eqref{1}: $ f $ is the difference of the values of a certain quadratic polynomial (i.e. $ g $) at the points $ v $ and $ u $.

---

* There are major problems with the way you've presented the question; so the rephrasing is necessary. I've tried to keep the rephrased version as close to the original one as possible. I try to list the problems, so that you could choose another version, in case you found my choices not suitable. The only unnecessary change that I've made is that I've chosen the index $ k $ to change from $ 0 $ to $ p $ instead of the original $ 1 $ to $ p + 1 $. This was only for the looks of it, and for being more in line with the convention that $ 0 $ is a natural number.

1. There's a problem with the notation "$ f [ a _ k ] $". The defining expression for it depends not only on the value of $ a _ k $, but also on the value of $ a _ { k + 1 } $. The resolution would be to take $ f $ to be either a function of both mentioned values (which is the one I've taken), or a sequence with $ k $ as an index: $ f _ k $ would be the value given by the expression containing both "$ a _ k $" and "$ a _ { k + 1 } $".
2. The expression $ \sum _ { i = a _ k } ^ { a _ { k + 1 } } ( \dots ) $ doesn't make much sense, as $ a _ k $ and $ a _ { k + 1 } $ are not supposed to be integers (and in fact, they won't be, as the solution shows). To use an alternative which makes sense, I've dealt with $ a _ k $ and $ a _ { k + 1 } $ "as if" they are integers with $ a _ k \le a _ { k + 1 } $, so that the summation makes sense. Then, I've also assumed that they are nonnegative, so that I could use the famous equation $ \sum _ { i = 0 } ^ m i = \frac { m ( m + 1 ) } 2 $, which holds for any nonnegative integer $ m $. Using this formula, I've rewritten the expression in a form that no summations appear in it. This way, we get an expression (which is in fact a polynomial) that makes sense for any real numbers as the value of its variables.
3. There seems to be miscalculations in your work. We can rewrite the recurrence relation you've got as $$ a _ { k + 2 } ( 2 n - a _ { k + 2 } - 1 ) - 2 a _ { k + 1 } ( 2 n - a _ { k + 1 } - 1 ) + a _ k ( 2 n - a _ k - 1 ) = 0 \text , \tag 4 \label 4 $$ and the resulting formula you've got as $$ a _ k = \frac 1 2 \left( 2 n + 1 - \sqrt { ( 2 n + 1 ) ^ 2 - \frac 4 p ( k - 1 ) n ( n + 1 ) } \right) \text . \tag 5 \label 5 $$ Also, for nonnegative integers $ u $ and $ v $ with $ u \le v $ we have $$ \sum _ { i = u } ^ v \big( n - ( i + 1 ) \big) = \sum _ { i = u } ^ v ( n - 1 ) - \left( \sum _ { i = 0 } ^ v i - \sum _ { i = 0 } ^ { u - 1 } i \right) \text , $$ and thus $$ f ( u , v ) = ( v - u + 1 ) ( n - 1 ) - \frac { v ( v + 1 ) - u ( u - 1 ) } 2 \text . \tag 6 \label 6 $$ Straightforward calculations show that neither \eqref{5} satisfies \eqref{4}, nor \eqref{4} is derived from \eqref{6} and \eqref{0}. To make things match, I've made two choices. First, I assumed that you meant to write "$ ( n - i + 1 ) $" as the summand instead of "$ n - ( i + 1 ) $". This changes the "$ n - 1 $" appearing in \eqref{5} to "$ n + 1 $". Second, I changed the bounds of the index of summation from $ u $ and $ v $ to $ u + 1 $ and $ v $. This means that we deal with summations of the form $ \sum _ { i = u + 1 } ^ v ( \dots ) $, which doing similar calculation as above, results in \eqref{1} instead. This way, instead of \eqref{4}, we get the recurrence relation $$ a _ { k + 2 } ( 2 n - a _ { k + 2 } + 1 ) - 2 a _ { k + 1 } ( 2 n - a _ { k + 1 } + 1 ) + a _ k ( 2 n - a _ k + 1 ) = 0 \text , $$ which is nothing but \eqref{2}, and the solution will be as in \eqref{3}, which nothing but \eqref{5} with a unit shift in the index $ k $. So, my choices are meant to keep the the formula you've given, but there will be a change in the recurrence relation. Another choice would be keeping \eqref{4} but losing \eqref{5}. This could be done by choosing the bounds of the index of summation to be $ u $ and $ v - 1 $, while letting the summand to be $ \big( n - ( i + 1 ) \big) $. These result in $$ f ( u , v ) = ( v - u ) ( n - 1 ) - \frac { v ( v - 1 ) - u ( u - 1 ) } 2 \text , $$ the recurrence relation \eqref{4}, and the solution $$ a _ k = \frac 1 2 \left( 2 n - 1 - \sqrt { ( 2 n - 1 ) ^ 2 - \frac 4 p k n ( n - 1 ) } \right) \tag 7 \label 7 $$ for $ k < p $ (and of course $ a _ p = n $, which is the result of a formula similar to \eqref{7}, but with a "$ + $" instead of the "$ - $" before the radical sign). The alternatives in which you keep the bounds of the summation index to be $ u $ and $ v $, which result in formulas for $ f $ like that in \eqref{6}, seem to be harder to treat.