Solving Problem by different Method ( non-induction)

Question

I have this problem , which I was able to prove it by induction, but I wonder could be solve by direct method ( for example combinatorial method).

I want to find number of solution for $$0 \le 4i+5j\le k$$ and we have the following restriciton $$ 0 \le i \le 4 \, \mbox{and} \, k\ge 11$$ . { the solution is of the form $(i,j)$ and only non-negative integer }. We only need to know the number of the solution.

Note:- By mathematical Inducation I show that number of solution is equal to $k-6$.

Answer 1

You can prove that there is only one solution to $$4i+5j=k$$ under the restrictions for each $i$, so that one "solution" gets added each time you increase $k$ by one.

To prove the claim, note that $$4=-1\hspace{2mm}(\text{mod} 5)$$ so that $$0(4)=0,1(4)=-1,2(4)=-2,\dots,4(4)=-4\hspace{2mm}(\text{mod} 5)$$

Now say that, for example $k=2\hspace{2mm}(\text{mod} 5)$. Then we will have to take $i=3$ so that $k-4i$ is divisible by 5 (note that $j$ is multiplied by 5).

Therefore the equation has exactly one solution, and now you just have to check that your claim holds for $k=11$.

Answer 2

An idea that I had was that $4i$ cycles through all residues modulo $5$. Any idea how to take it from here?