OFFSET
1,2
COMMENTS
The question originated from the first puzzle 'Low Budget' in the book Mathematical Puzzles and Curiosities.
REFERENCES
I. David, T. Khovanova, and Y. Shpilman, Mathematical Puzzles and Curiosities, World Scientific, 2026, p. 2.
LINKS
Paolo Xausa, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).
FORMULA
a(n) = n*(n^2+8)/6 - (15 - 3*(-1)^n)/12, for n > 1.
a(n) = A026035(n) + n - 1, for n > 1.
a(n) = A110611(n-1) + n, for n > 1.
G.f.: x*(1 + 2*x^3 - 2*x^4 + x^5)/((1 - x)^4*(1 + x)). - Stefano Spezia, Feb 20 2026
From Enrique Navarrete, Feb 25 2026: (Start)
For n>1, a(n) = (n^3 + 8*n - 6)/6, n even; a(n) = (n^3 + 8*n - 9)/6, n odd.
For n>6, a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5).
E.g.f.: 1 + x + (1/12)*((2*x^3 + 6*x^2 + 18*x - 15)*exp(x) + 3*exp(-x)). (End)
EXAMPLE
For n=4, we buy 4 vouchers in the following order 3,2,1,4. The cost is 3+3*2+2*1+1*4=15, which is the smallest possible cost. For contrast, if we buy the vouchers in order 1,2,3,4, the cost is 1+1*2+2*3+3*4 = 21, which is larger. Thus, a(4)=15.
MATHEMATICA
LinearRecurrence[{3, -2, -2, 3, -1}, {1, 3, 7, 15, 26, 43}, 60] (* Paolo Xausa, Mar 03 2026 *)
PROG
(PARI) a(n)= (n^3 + 8*n - n%2*3)/6 - (n>1) \\ Ruud H.G. van Tol, Mar 03 2026
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Tanya Khovanova and PRIMES STEP junior group, Feb 02 2026
STATUS
approved
