Find the sum $S=\sum\limits_{k=1}^{n} {4k-1 \choose k}$

Question

Find the sum $S=\sum\limits_{k=1}^{n} {4k-1 \choose k}$
I tried using the Pascal's identity to get $S=\sum\limits_{k=1}^{n} {4k \choose k}-{4k-1 \choose k-1}$ ,but it is not really telescopic.
Any suggestions?

Answer 1

Hint:

The general term of $$(x^a+x^b)^{4k-1}$$ is $$\binom{4k-1}rx^{a(4k-1-r)}x^{br}$$

$r=k\implies \binom{4k-1}k x^{a(3k-1)+bk}$

To eliminate $k$ in the exponent of $x$

set $3a+b=0\iff b=-3a$

WLOG $a=-1,b=?$

We need to find the coefficient of $x$ in $$\sum_{k=1}^n(x^{-1}+x^3)^{4k-1}$$ which is a finite Geometric Sequence