We consider an SOS (solid-on-solid) model, with spin values from the set of all integers, on a Cayley tree of order k and are interested in translation-invariant gradient Gibbs measures (GGMs) of the model. Such a measure corresponds to a boundary law (a function defined on vertices of the Cayley tree) satisfying a functional equation. In the ferromagnetic SOS case on the binary tree we find up to five solutions to a class of 4-periodic boundary law equations (in particular, some 2-periodic ones). We show that these boundary laws define up to four distinct GGMs. Moreover, we construct some 3-periodic boundary laws on the Cayley tree of arbitrary order k, which define GGMs different from the 4-periodic ones.