| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Suppose you have a non-trivial sequence of numbers such that each element is the sum of the k previous elements. Is it possible for the sequence to be periodic? (This problem is from Prof. Walter Mientka, and originated with one of his students. It's been making the rounds on the usenet, with some interesting results, but there *is* a simple solution).
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 681.1 | Yes! | VIDEO::OSMAN | Eric, dtn 223-6664, weight 146 | Mon Mar 23 1987 17:13 | 0 |
| 681.2 | CLT::GILBERT | eager like a child | Mon Mar 23 1987 21:35 | 1 | |
The trivial solutions have all elements equal to some constant, of course. | |||||
| 681.3 | CLT::GILBERT | eager like a child | Sun Apr 12 1987 16:01 | 10 | |
Spoiler follows. Let x[n] = Sum (i=1 to k) of x[n-i]. Then x[n+1] - x[n] = x[n] - x[n-k], or x[n] = (x[n+1]+x[n-k])/2. If the sequence is periodic, there must be a maximal element -- let it be x[m]. But x[m] is the average of two other elements (x[m+1] and x[m-k]); thus these three must all be equal. Since x[m] = x[m+1], x[m+1] is also a maximal element, and the same analysis implies that *all* the elements are equal. Thus, there are only trivial solutions -- all elements equal. | |||||