So I have a problem that requires me to process all the combinations of $n$ elements in a given set (let's say $S$). I know that I can get the number of combinations using $||S|| \choose n$.
But then I discovered that I can also solve my problem by processing all the combination of a first element in a subset (let's say $S'$) of $S$ and $n-1$ elements in $S$. So I wrote the formula that I thought could give me the new number of combinations, it's something along: $||S'|| * {||S||-1 \choose n-1}$
The problem is, this new formula gives me more combinations than the first one once $n$ is greater than a certain number.
So here is my question: if the second formula is correct, how is it possible that I get more combination while choosing the first element in a smaller set (as it's a subset of $S$), if it is not, what am I missing ?
The way I see it, your question is two-fold.
I will try to match notation as best I can, but will give some flavor as to what each object is by creating a hypothetical scenario with which to work.
Paschal's Identity is useful to break apart a combination into two smaller combinations. We arbitrarily specify one of the elements to be "special" (for example, the smallest element). We notice that of all of the combinations of size $n$ of the set $S$, they can be categorized as either containing the special element (and $n-1$ others) or not containing the special element (thus needing $n$ others).
This brings us to the identity $\binom{\|S\|}{n} = \binom{\|S\setminus \{x\}\|}{n-1}+\binom{\|S\setminus\{x\}\|}{n} = \binom{\|S\|-1}{n-1}+\binom{\|S\|-1}{n}$
So, how about if $S'$ is a subset of $S$ which has more than just one element? That is to say, how about if $S'$ is the set of "special" elements of $S$?
Similar logic applies, and brings us to Vandermonde's Identity.
Instead of breaking up into the cases of "the combination contains the special element" and "the combination doesn't contain the special element", we have more cases to consider. We instead break it up into cases based on how many special elements are used. It could range anywhere from $0$ to $\|S'\|$. We then note that the number of combinations which use $k$ special elements must use $n-k$ not-special elements. Picking which ones are the special and which aren't and applying multiplication principle yields the result.
This brings us to the identity: $\binom{\|S\|}{n} = \sum\limits_{k=0}^{\|S'\|} \binom{\|S'\|}{k}\binom{\|S\setminus S'\|}{n-k} = \sum\limits_{k=0}^{\|S'\|}\binom{\|S'\|}{k}\binom{\|S\|-\|S'\|}{n-k}$
Note that Paschal's identity is just a special case of Vandermonde's where $\|S'\|=1$.
We turn our attention now to the expression you have written. By fundamental principles of counting, if two expressions correctly count the same scenario, they must be equal. Since your expression is not equal to $\binom{\|S\|}{n}$ it must count something different than simply the number of combinations of size $n$, but what does it actually count?
Here I give a hypothetical scenario. Let $S$ be a set of members of a large committee. Let $S'$ be the subset of the members of $S$ who have been selected as potential candidates to lead a special subcommittee.
We ask how many ways we can select a subcommittee with a total of $n$ people with a specific leader who is from the list of available candidates. (the ordinary members of the subcommittee are allowed to be from the list of candidates as well as from the ordinary committee members)
There are then $\|S'\|\binom{\|S\|-1}{n-1}$ number of subcommittees with a leader from a list of available candidates.
As an aside: Paschals Identity and Vandermonde's Identity are often instead written as the following:
$\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}$
$\binom{m+n}{r} = \sum\limits_{k=0}^r \binom{m}{k}\binom{n}{r-k}$