binomial-coefficients
Consider these two linear equation:
$$ 2a \binom{18}{j-1} – 4b \binom{18}{j} = \binom{18}{j-2}$$
True for $j=16,17$, find $a$ and $b$
This came up as part of a problem I was doing.. expanding everything out and doing it really ugly. Are there any tricks I could use to solve the system fast considering they are involving binomial coefficients? One thing I've considered doing is adding both equations and pascal's identity but not sure if that actually makes anything easier.
There is a cute argument for $b=c+1$ though I don't know how to pull it through in the general case.
Let $U$ be the set of ordered $c+1$-tuples of sets of cardinality $c$ in which no set repeats. Then, obviously, $|U|=(c+1)!{{n\choose c}\choose c+1}$. Let $V$ be the set of ordered $c$-tuples of sets of cardinality $c+1$ in which no set repeats. Then $|V|=c!{{n\choose c+1}\choose c}$. Now take any element of $V$, i.e., an ordered family of sets $A_1,\dots,A_{c}$. Take any $a_1\in A_1$ ($c+1$ choices). Suppose that $a_1\in A_1,\dots,a_k\in A_k$ are already chosen. Then we want to choose $a_{k+1}\in A_{k+1}$ so that $a_{k+1}\ne a_j$ and $A_{k+1}\setminus \{a_{k+1}\}\ne A_j\setminus\{a_j\}$ for all $j=1,\dots,k$. Suppose that we have $\ell$ prohibitions of the first type. Then, if we honor them, the prohibitions of the second type for the corresponding sets will be honored automatically (if $a_j\in A_{k+1}$ and we don't remove it, then surely $A_{k+1}\setminus \{a_{k+1}\}\ne A_j\setminus\{a_j\}$. The remaining $k-\ell$ sets introduce at most one prohibition of the second type each, so we have $\le k$ prohibitions total. Thus we have $\ge c+1-k$ choices for $a_{k+1}$. Once we run the whole procedure, the reduced sets $A_j$ listed in the same order and the set $\{a_1,\dots,a_c\}$ listed last will constitute an element of $U$ and each element of $V$ will generate $\ge(c+1)!$ different elements of $U$ (by different choices of $a_1,\dots,a_c$. On the other hand, each element of $U$ can be obtained from at most $c!$ elements of $V$ (that is the number of ways to distribute the elements of the last $c+1$-st set among the first $c$. This immediately gives a non-strict inequality you want. To make it strict, you need to assume $c>1$ and $n\ge c+1$ (otherwise you have equality), in which case the ordered sequence of sets $A_j=\{1,2,\dots,c+1\}\setminus\{j\}$ has fewer than $c!$ distribution options (none at all, really) resulting in a legitimate element of $V$.
Edit (the general case)
In this case it will be convenient to define $U$ as the set of all ordered $b$-tuples of sets of cardinality $c$ such that the sets are pairwise different (as sets), the first $c$ sets are unordered, and the last $b-c$ sets are ordered. Then $|U|=b!(c!)^{b-c}{{n\choose c}\choose b}$. Let $V$ be the same as before (ordered $c$-tuples of unordered subsets of cardinality $b$ in which the sets are pairwise different), so $|V|=c!{{n\choose b}\choose c}$.
Now let $\langle A_1,\dots, A_c\rangle$ be an element of $V$. We want to remove $b-c$ elements $a_{j,1},a_{j,2},\dots,a_{j,b-c}$ from $A_j$ and form $b-c$ new ordered sets $B_k=\langle a_{1,k},a_{2,k},\dots, a_{c,k}\rangle$ ($k=1,\dots,b-c$) to get an element of $U$.
To this end start with choosing $a_{1,1},\dots,a_{1,b-c}\in A_1$ in an arbitrary way, which gives $b(b-1)\dots(b-c+1)$ choices. Now, when choosing $a_{k+1,1}\in A_{k+1}$ for $k\ge 1$, add to the standard prohibitions $a_{k+1,1}\ne a_{j,1}$, $A_{k+1}\setminus\{a_{k+1,1}\}\ne A_j\setminus\{a_{j,1}\}$ ($j\le k$), which exclude at most $k$ elements just as before, the prohibitions $a_{k+1,1}\ne a_{1,m}$ ($m>1$), which exclude additional $b-c-1$ elements at most, leaving $c+1-k$ choices as before. These additional prohibitions guarantee that the set $B_1=\{a_{1,1},a_{2,1},\dots, a_{c,1}\}$ does not contain any of the elements $a_{1,m}$ ($m>1$) and, therefore, will be different from every set $B_m$ ($m>1$) as an unordered set and we still have $c!$ choices.
Having constructed $B_1$, we construct $B_2$ with the standard restrictions $a_{k+1,2}\ne a_{j,2}$, $A_{k+1}\setminus\{a_{k+1,1},a_{k+1,2}\}\ne A_j\setminus\{a_{j,1},a_{j,2}\}$ ($j\le k$) and additional restrictions $a_{k+1,2}\ne a_{1,m}$ but now with $m>2$. This gives $c!$ choices again, and so on. Thus, from each element of $V$, we get $b(b-1)\dots(b-c+1) (c!)^{b-c}$ distinct elements of $U$. The recovery of an element of $V$ from an element of $U$ is now possible in just one way, if at all, which, again, gives a non-strict inequality. I leave it to you to figure out when and how it becomes strict in this case.
Ok, I think I've found an answer along with a proof. I will go through a series of claims (of course there may be more efficient ways of going about this). The main result is in Claim 3.
Claim 1. For nonnegative integers $m, r, t$ we have $$ \sum_{j=0}^{m+t} \binom{m+t}{j}\binom{j+r}{t+r}(-1)^{j} = (-1)^{m+t}\binom{r}{m}. \tag*{$(1)$} $$
Proof. We proceed by Egorychev's method. We will use the fact that $$ \binom{j+r}{t+r} = \frac{1}{2\pi i}\oint \frac{(1+z)^{j+r}}{z^{t+r+1}} \, dz, $$ where the integral is a contour integral over a circle $|z|=\varepsilon$ for some $0<\varepsilon<\infty$. Using this fact, and interchanging the summation and integral signs when necessary, we have \begin{align*} \sum_{j=0}^{m+t} \binom{m+t}{j}\binom{j+r}{t+r}(-1)^{j} &= \sum_{j=0}^{m+t} \binom{m+t}{j} \left( \frac{1}{2\pi i}\oint \frac{(1+z)^{j+r}}{z^{t+r+1}} \, dz \right) (-1)^{j} \\[1.2ex] &= \frac{1}{2\pi i}\oint \; \sum_{j=0}^{m+t} \binom{m+t}{j} \frac{(1+z)^{j+r}}{z^{t+r+1}} (-1)^{j} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{t+r+1}} \; \sum_{j=0}^{m+t} \binom{m+t}{j} (1+z)^{j} (-1)^{j} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{t+r+1}} \; \sum_{j=0}^{m+t} \binom{m+t}{j} (-1-z)^{j} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{t+r+1}} (1 - 1 - z)^{m+t} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{t+r+1}} (-z)^{m+t} \, dz \\[1.2ex] &= \frac{1}{2\pi i}\oint \frac{(1+z)^{r}}{z^{r-m+1}} (-1)^{m+t} \, dz \\[1.2ex] &= (-1)^{m+t}\binom{r}{r-m} \\[1.2ex] &= (-1)^{m+t}\binom{r}{m}. \end{align*} $$\tag*{$\blacksquare$}$$
Claim 2. For nonnegative integers $n, r, s$ with $s\ge r$, we have $$ \sum_{k=0}^{n} \binom{n-r}{k-r}\binom{k}{s}(-1)^{k} = (-1)^{n}\binom{r}{n-s}. \tag*{$(2)$} $$
Proof. If $s > n$, then both sides of $(2)$ are clearly $0$, so for the proof let us assume $s\le n$. Take $m = n-s$ and $t = s-r$ and plug these into $(1)$. We obtain $$ \sum_{j=0}^{n-r} \binom{n-r}{j}\binom{j+r}{s}(-1)^{j} = (-1)^{n-r}\binom{r}{n-s}. $$ We can shift the summation index by taking $j = k-r$ (where $k$ is the new index). By doing this and then multiplying both sides by $(-1)^{r}$, we get $(2)$. $$\tag*{$\blacksquare$}$$
Claim 3. For nonnegative integers $n, r, s$, we have $$ \boxed{ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = (-1)^{n}\binom{n}{n-r,\, n-s,\, r+s-n} } $$ where the RHS involves the multinomial coefficient.
Proof. Without loss of generality, assume $s\ge r$. Consider the fact that $$ \binom{n}{k}\binom{k}{r} = \binom{n}{r}\binom{n-r}{k-r} $$ and use this to obtain $$ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = \binom{n}{r}\sum_{k=0}^{n} \binom{n-r}{k-r}\binom{k}{s}(-1)^{k}. $$ By Claim 2, we see that the RHS reduces to $$ \binom{n}{r}\cdot (-1)^{n}\binom{r}{n-s}. $$ This is then decomposed as \begin{align*} \binom{n}{r}\cdot (-1)^{n}\binom{r}{n-s} &= (-1)^{n} \frac{n!}{r!(n-r)!}\frac{r!}{(n-s)!(r-n+s)!} \\ &= (-1)^{n}\frac{n!}{(n-r)!(n-s)!(r+s-n)!}, \end{align*} and the fraction in the last expression can be identified as a multinomial coefficient, giving us $$ \sum_{k=0}^{n}\binom{n}{k}\binom{k}{r}\binom{k}{s}(-1)^{k} = (-1)^{n}\binom{n}{n-r,\, n-s,\, r+s-n} $$ as desired. $$\tag*{$\blacksquare$}$$
Best Answer
$$\frac{\binom{n}{r}}{\binom{n}{r-1}}=\frac{n+1-r}{r}$$ Thus, if you divide both side of the equation by $\binom{18}{j-1}$ , then you can simplify it and that will decrease your calculations.