MathDB

3

Part of 2024 VJIMC

Problems(2)

Inequality with degrees in simple graph implies triangle

Source: VJIMC 2024, Category I, Problem 3

4/14/2024
Let nn be a positive integer and let GG be a simple undirected graph on nn vertices. Let did_i be the degree of its ii-th vertex, i=1,…,ni = 1, \dots , n. Denote Δ=max⁡di\Delta=\max d_i. Prove that if ∑i=1ndi2>nΔ(n−Δ),\sum_{i=1}^n d_i^2>n\Delta(n-\Delta), then GG contains a triangle.
inequalitiesgraphdegreecombinatorics
Recurrence sequence grows like sqrt(2log n)

Source: VJIMC 2024, Category II, Problem 3

4/14/2024
Let a1>0a_1>0 and for n≥1n \ge 1 define an+1=an+1a1+a2+⋯+an.a_{n+1}=a_n+\frac{1}{a_1+a_2+\dots+a_n}. Prove that lim⁡n→∞an2ln⁡n=2.\lim_{n \to \infty} \frac{a_n^2}{\ln n}=2.
recurrence relationSequenceslimitasymptotic behaviourreal analysis