The topic of recurrence relations has recently been introduced in many discrete mathematics textbooks. Recurrence relations are efficient modelling and problem-solving techniques used in mathematics. Combinatorial problems are often used to introduce recurrence relations. However, many textbooks consider problems that can be reduced only to the recurrence relations of the first or second order. To overcome this problem, in this paper, we propose a general combinatorial problem of path tiling with tiles of different sizes and colours. For especially selected tile sizes and for certain tile colours, the problem can be reduced to solving a recurrence relation of the third, fourth, or higher orders. Furthermore, through actual examples, we show that various cases can be derived from the roots of a characteristic equation: different real roots, different real and complex roots, and repeated real roots with different multiplicities. We hope that the presented problems will provide teachers with the opportunity to present this topic with better content.