Ramsey Number Inequality: $R(\underbrace{3,3,...,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,...3}_k)-1)+2$ I want to prove that:
$$R(\underbrace{3,3,...,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,...3}_k)-1)+2$$
where R is a Ramsey number. In the LHS, there are $k+1$ $3$'s, and in the RHS, there are $k$ $3's$. I really have no clue how to start this proof. Any help is appreciated!

The general strategy will probably look something like this.  (Let $R =  R(\underbrace{3,\ldots,3}_k)$ in what follows.)


*

*Take $k+1$ copies of $K_{R-1}$, the complete graph on $R-1$ vertices, and assume that the edges of  each one are colored with $k+1$ colors so as to avoid monochromatic triangles.

*Then suppose that no copy contains a triangle in the $k+1$'th color.

*Then show that if you add 2 more vertices $u,v$ there must be some monochromatic triangle unless (something about the edges between $u$ and the $K_{R-1}$'s, and between $v$ and the $K_{R-1}$'s).

*Then show that the edge from $u$ to $v$ must complete a monochromatic triangle with some vertex in one of the $K_{R-1}$'s.
A more careful analysis would consider the many edges between one $K_{R-1}$ and another, but with any luck you won't have to do that.
On review, I think Alex's suggestion of induction on $k$ is probably an excellent one.
