Is $\frac{k!!}{j!!(k-j)!!}\leq\frac{k!}{j!(k-j)!}$ for all integers $j$ and $k$, where $0\leq j\leq k$? For all integers $j$ and $k$, where $0\leq j\leq k$, is the inequality 
$\frac{k!!}{j!!(k-j)!!}\leq\frac{k!}{j!(k-j)!}$ 
true?
I have a feeling that it is and it would be helpful to me if it is, but I do not know how to go about proving it besides cancelling out the factors that are on both the left and right sides. 
Eventually, I want to show that $\sum_{j=0}^k\frac{k!!}{j!!(k-j)!!}\leq\sum_{j=0}^k\frac{k!}{j!(k-j)!}=2^k$.
 A: If you look at http://en.wikipedia.org/wiki/Double_factorial, you will find interesting relation between double factorials and factorials, namely, for odd values
$$(2k-1)!!=\frac{2^{-k} (2 k)!}{k!}$$ and $$(2k)!!=2^k k!$$ for even values. This could help you significantly for your first question.  
For your last question, it is a problem I worked a long time ago in the area of statistical thermodynamics and, for your left hand side term, I arrived, for the summation, to an ugly formula which is
$$\frac{2^{\frac{1}{2} \left(-(-1)^k-1\right)} \pi ^{\frac{(-1)^k}{2}} \Gamma
   \left(\frac{k+2}{2}\right) \left(2 \,
   _2F_1\left(1,\frac{1-k}{2};\frac{3}{2};-1\right) \Gamma
   \left(\frac{k+3}{2}\right)-\, _2F_1\left(\frac{1}{2},1;\frac{k+3}{2};-1\right)
   \Gamma \left(\frac{k+1}{2}\right)\right)}{\Gamma \left(\frac{k+1}{2}\right) \Gamma
   \left(\frac{k+3}{2}\right)}+2^{k/2}$$ that I have never been able to simplify. This is alway smaller than $2^k$.  
Plotting the ratio of this monster to $2^k$ as a function of $k$, the points align on two curves (one for odd values of $k$, the other for even values of $k$) which shows,as one could expect, an exponential decrease.  
As Newb wrote in his answer, take care that $j>2$ is a required condition.
