(Proposed by Esteban Arreaga, Renan Finder and José Madrid, IMPA, Rio de Janeiro)
Solution 1. We prove by induction on k. If k=1 then we have f(n)=2n+1 and the statement immediately follows from the AM-GM inequality.
Assume that k≥2 and the statement is true for k−1. Let g(m) be the number of integer solutions of ∣x1∣+…+∣xk−1∣≤m; by the induction hypothesis g(m−1)g(m+1)≤g(m)2 holds; this can be transformed to
g(1)g(0)≤g(2)g(1)≤g(3)g(2)≤….
For any integer constant c, the inequality ∣x1∣+…+∣xk−1∣+∣c∣≤n has g(n−∣c∣) integer solutions. Therefore, we have the recurrence relation
f(n)=c=−n∑ng(n−∣c∣)=g(n)+2g(n−1)+…+2g(0).
It follows that
f(n)f(n−1)=g(n)+2g(n−1)+…+2g(1)+2g(0)g(n−1)+2g(n−2)+…+2g(0)≤≤g(n+1)+g(n)+(g(n)+…+2g(1)+2g(0))g(n)+g(n−1)+(g(n−1)+…+2g(0)+2⋅0)=f(n+1)f(n)
as required.
Solution 2. We first compute the generating function for f(n):
n=0∑∞f(n)qn=(x1,x2,…,xk)∈Zk∑c=0∑∞q∣x1∣+∣x2∣+⋯+∣xk∣+c=(x∈Z∑q∣x∣)k1−q1=(1−q)k+1(1+q)k.
For each
a=0,1,… denote by
ga(n) (n=0,1,2,…) the coefficients in the following expansion:
(1−q)k+1(1+q)a=n=0∑∞ga(n)qn.
So it is clear that
ga+1(n)=ga(n)+ga(n−1) (n≥1),
ga(0)=1. Call a sequence of positive numbers
g(0),
g(1),
g(2),
… good if
g(n)g(n−1) (n=1,2,…) is an increasing sequence. It is straightforward to check that
g0 is good:
g0(n)=(kk+n),g0(n)g0(n−1)=k+nn.
If
g is a good sequence then a new sequence
g′ defined by
g′(0)=g(0),
g′(n)=g(n)+g(n−1) (n≥1) is also good:
g′(n)g′(n−1)=g(n)+g(n−1)g(n−1)+g(n−2)=1+g(n−1)g(n)1+g(n−1)g(n−2),
where define
g(−1)=0. Thus we see that each of the sequences
g1,
g2,
…,
gk=f are good. So the desired inequality holds.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 2–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.