In this paper, we present a mathematical model of the formation of gullies at the downstream end of plateaus composed of weakly cohesive fine material such as freshly deposited volcanic ash as an extension of the theory of channel inception on purely erosional slopes proposed by Izumi and Parker (2000). We perform a linear stability analysis using the momentum equations of flow, the transport equation of suspended sediment, and the Exner equation for beds subject to both erosion and deposition of bed material. We find from the analysis that deposition leads to uniform growth of perturbations at small wave numbers (or large wavelengths) and suppresses the dominant wavelength associated with the maximum growth rate. When the effect of deposition increases further, channel initiation itself tends to be inhibited. As long as the effect of deposition is not large, slopes become unstable to transverse perturbations, and the dominant wavelength appears in the range of 6--15 times the Froude critical depth of the sheet flow on slopes, divided by the bottom friction coefficient. Assuming that the bottom friction coefficient is of the order of 0.01, we find that the dominant gully spacing is of the order of 1000 times the Froude critical depth, which is similar to the result obtained in the case without deposition. We find that deposition affects channel initiation itself rather than channel spacing.