Question on induction regarding monochromatic triangles in graph colourings- Homework related

Question

Let $k$ be a natural number and for each $k$ let $r_k$ be the minimum number $n$ so that if we colour the edges of $K_n$ with $k$ colours then we can find a monochromatic triangle.

I have so far showed that $r_k − 1 ≤ k(r_{k-1} − 1) + 1$ and now I have been asked to do the following:

Use induction to deduce that for each $k$,

$r_k − 1 ≤ k!( 1 + 1 + 1/2! + 1/3! + · · · + 1/k!) ≈ ek!$

I so far have that if we define $u_k$ to be $k!(1+1+1/2!+....+1/k!) $ then we have that $u_k=ku_{k-1}+1. $ Can anyone help me from here?

Answer 1

The "roughly equals" bit is just the truncation of the Taylor expansion for $e = \exp(1)$ to $k$ terms.

For the first inequality, you've got a recursive definition of $u_k$. Can you use that definition to show that $r_k - 1 \leq u_k$ for all $k$?

• The base case is $u_1 = 1+1 = 2$ while $r_1 -1 = 3-1 = 2$.
• The step $1 \Rightarrow 2$ is: $r_1 - 1 \leq u_1$, so $u_2 = 2 u_{1} + 1 \geq 2 (r_1 - 1) + 1 \geq (r_2 - 1)$

Can you extend that?