IMC 2016/2/4

#1

Έστω θετικός ακέραιος

. Για κάθε μη αρνητικό ακέραιο

συμβολίζουμε με f(n)

το πλήθος των $(x_1,\ldots,x_k) \in \mathbb{Z}^k$ τα οποία ικανοποιούν $|x_1| + \cdots + |x_k| \leqslant n$ .

Να δειχθεί ότι $f(n-1)f(n+1) \leqslant f(n)^2$ για κάθε $n \geqslant 1$ .

#2

Ας υπολογίσουμε πρώτα το f(n)

.

Θα μετρήσουμε αρχικά το πλήθος των λύσεων της $|x_1| + \cdots + |x_k| \leqslant n$ όπου ακριβώς

από τα

είναι διάφορα του

.

Έχουμε $\displaystyle{\binom{k}{r}}$ τρόπους να επιλέξουμε ποια δεν θα ισούνται με

και

επιλογές για το πρόσημο των μη μηδενικών στοιχείων. Μένει να βρούμε πόσες λύσεις έχει η $y_1 + \cdots + y_r \leqslant n$ στους θετικούς ακεραίους.

Ισοδύναμα θέλουμε το πλήθος των λύσεων της $y_1 + \cdots + y_r + y_{r+1} = n+1$ στους θετικούς ακεραίους. Είναι γνωστό ότι η απάντηση ισούται με $\binom{n}{r}$ . [Αν δεν το γνωρίζετε δοκιμάστε το!]

Καταλήγουμε στο $\displaystyle{ f(n) = \sum_{r=0}^k 2^r \binom{k}{r} \binom{n}{r}}$

Θέτω $\displaystyle{a_r = 2^r \binom{n}{r}}$ και $b_r = \binom{k}{r}$ .

Ονομάζω μια ακολουθία $(c_n)_{n \geqslant 0}$ μη αρνητικών αριθμών log-concave αν
(α) $c_n^2 \geqslant c_{n-1}c_{n+1}$ για κάθε $n \geqslant 1$ και
(β) Η ακολουθία δεν έχει ενδιάμεσες μηδενικές τιμές. Δηλαδή αν c_n = 0

τότε είτε

για κάθε

είτε

για κάθε

.

Θέλω να δείξω ότι η f(n)

είναι log-concave.

Είναι γνωστό (και απλό) ότι οι (a_r)

και

είναι log-concave.

Αρκεί να δείξω ότι αν οι ακολουθίες (a_r),(b_r)

είναι log-concave το ίδιο ισχύει και για την ακολουθία $\displaystyle{ c_n = \sum_{r=0}^k a_rb_{k-r}}$

Θέλω λοιπόν να δείξω ότι

$\displaystyle{\sum_r \sum_s a_ra_s b_{k-r}b_{k-s} \geqslant \sum_r \sum_s a_ra_sb_{k+1-r}b_{k-1-s} \qquad (\ast) }$

Παρατηρώ αρχικά ότι $r \leqslant s \implies a_ra_s - a_{r-1}a_{s+1} \geqslant 0}$ . Πράγματι
- Αν $a_{r-1} = 0$ η ανισότητα είναι προφανής.
- Αν τα $a_{r-1},\ldots,a_s$ είναι όλα διάφορα του

, τότε είναι
$\displaystyle{ \frac{a_r}{a_{r-1}} \geqslant \frac{a_{r+1}}{a_r} \geqslant \cdots \geqslant \frac{a_{s+1}}{a_s}}$
- Αν a_t = 0

για κάποιο $t \in \{r,r+1,\ldots,s\}$ τότε είτε $a_s = a_{s+1} = 0$ είτε $a_r = a_{r-1} = 0$ . Και στις δύο περιπτώσεις η ανισότητα είναι προφανής.

Ομοίως έχω $r \geqslant s \implies a_ra_s - a_{r-1}a_{s+1} \leqslant 0}$ .

Ανάλογες ανισότητες ισχύουν ασφαλώς και για τα b_i

. Οπότε για κάθε r,s

έχω

$\displaystyle{ (a_ra_s - a_{r-1}a_{s+1})(b_{k-r}b_{k-s} - b_{k-r+1}b_{k-s-1}) \geqslant 0}$

το οποίο δίνει

$\displaystyle{ a_ra_sb_{k-r}b_{k-s} + a_{r-1}a_{s+1}b_{k-r+1}b_{k-s-1} \geqslant a_ra_sb_{k-r+1}b_{k-s-1} + a_{r-1}a_{s+1}b_{k-r}b_{k-s}}$

Προσθέτοντας λαμβάνω την $(\ast)$ όπως ήθελα. [Τα αθροίσματα είναι πεπερασμένα οπότε δεν υπάρχει οποιοδήποτε θέμα σύγκλισης.]

#3

Δημήτρη ωραία απόδειξη!
Μπορούμε να κάνουμε ένα διαφορετικό τελείωμα ως εξής:

Demetres έγραψε: Θέλω να δείξω ότι η είναι log-concave.

Είναι γνωστό (και απλό) ότι οι και είναι log-concave.

Αρκεί να δείξω ότι αν οι ακολουθίες είναι log-concave το ίδιο ισχύει και για την ακολουθία $\displaystyle{ c_n = \sum_{r=0}^k a_rb_{k-r}}$

Αυτό ισχύει γενικά: Αν έχουμε δύο συναρτήσεις που είναι log-concave, τότε η συνέλιξή τους (convolution) είναι επίσης log-concave και τελειώσαμε.
Η απόδειξη γίνεται μέσω της ανισότητας Prékopa–Leindler.
Δείτε πχ εδώ: https://en.wikipedia.org/wiki/Logarithm ... e_function

IMC 2016/2/4

IMC 2016/2/4

Re: IMC 2016/2/4

Re: IMC 2016/2/4

Μέλη σε σύνδεση