How can the speed of sound increase with an increase in temperature? I was reading a textbook. I found that it was mentioned the speed of sound increases with increase in temperature. But sound is a mechanical wave, and it travels faster when molecules are closer. 
But an increase in temperature will draw molecules away from each other, and then accordingly the speed of sound should be slower. How is it possible that the speed of sound increases if temperature increases? What is the relation of speed of sound and temperature?
 A: Great question.  The short answer is that your intuition (about dense stuff having faster speeds of sound) is probably influenced by different materials at the same temperature and is tainted by solids, when the issue here is really about gasses, which are different.
Let's look at some data:

Air is sparse, and has a low speed of sound of 760 mph.  The heavier things like copper are dense, and have a faster speed of sound.  Steel has a speed of sound of 10,000 mph!
So your intuition is not too bad, right?
What about cold air vs. hot air?  The cold air is denser, but has a lower speed of sound!  Here is where we can see your lovely paradox.
It turns out that repulsion due to external compression waves (what you called mechanical waves) in a solid like a metal are created from different mechanisms than a compressible gas.  A pressure wave in a solid will compress relatively stationary ions in a lattice.  The lattice is very strong, and the atoms aren't moving, but they can vibrate.  If you squeeze some steel, you are compressing this lattice a little, but the functional dependence of the electric fields in this lattice is rather complex.  In regards to the question here, one hopefully obvious result is that the dependence upon temperature won't be too strong, since the force(distance) function determines how quickly a disturbance travels through the lattice and the energy you give to the atoms in the lattice won't change much the lattice-distance-force curve relationship of interest here.
A gas is a much different beast in that there are just a bunch of independent particles flying around.  Here, the speed of sound is, basically, a weighted average of the faster gas molecules which of course move with the square root of the energy/temperature.  
In comparison to a solid, the question of what is the speed of sound in a gas is totally trivial.  Read this or this or to get an idea of how much more complex solids are.  If I gave physicists just the atomic properties (not things like the bulk modulus) of a solid like copper and also of a gas like O$_\rm 2$, they would only be able to compute, at least with a simple calculator, the speed of sound in O$_\rm 2$.  
A quick way to fix your intuition is to note the speed of sound in a solid at absolute zero vs. a gas.  Only the latter is zero.  Indeed, that's why gases can't exist near absolute zero.  The molecules in a cold enough gas don't even have enough energy to get away from each other, so they have to be a liquid or solid instead.
Hopefully you now see that your past experiences really only applied for different materials, not for individual materials as a function of temperature.
A: The speed of sound is given by:
$$v = \sqrt{\gamma\frac{P}{\rho}} \tag{1} $$
where $P$ is the pressure and $\rho$ is the density of the gas. $\gamma$ is a constant called the adiabatic index. This equation was first devised by Newton and then modified by Laplace by introducing $\gamma$.
The equation should make intuitive sense. The density is a measure of how heavy the gas is, and heavy things oscillate slower. The pressure is a measure of how stiff the gas is, and stiff things oscillate faster.
Now let's consider the effect of temperature. When you're heating the gas you need to decide if you're going to keep the volume constant and let the pressure rise, or keep the pressure constant and let the volume rise, or something in between. Let's consider the possibilities.
Suppose we keep the volume constant, in which case the pressure will rise as we heat the gas. That means in equation (1) $P$ increases while $\rho$ stays constant, so the speed of the sound goes up. The speed of sound is increasing because we're effectively making the gas stiffer.
Now suppose we keep the pressure constant and let the gas expand as it's heated. That means in equation (1) $\rho$ decreases while $P$ stays constant and again the speed of sound increases. The speed of sound is increasing because we're making the gas lighter so it oscillates faster.
And if we take a middle course and let the pressure and the volume increase then $P$ increases and $\rho$ decreases and again the speed of sound goes up.
So whatever we do, increasing the temperature increases the speed of sound, but it does it in different ways depending on how we let the gas expand as it's heated.
Just as a footnote, an ideal gas obeys the equation of state:
$$ PV = nRT \tag{2} $$
where $n$ is the number of moles of the gas. The (molar) density $\rho$ is just the number of moles per unit volume, $\rho = n/V$, which means $n = \rho V$. If we substitute for $n$ in equation (2) we get:
$$ PV = \rho VRT $$
which rearranges to:
$$ \frac{P}{\rho} = RT $$
Substitute this into equation (1) and we get:
$$ v = \sqrt{\gamma RT} $$
so:
$$ v \propto \sqrt{T} $$
which is where we came in. However in this form the equation conceals what is really going on, hence your confusion.
Experimentally, the constant of proportionality for the above equation is approx. 20.
A: Sound waves propagate through a medium as the result of collisions between molecules.  At higher temperatures, molecules have greater kinetic energy, and as they move faster their collisions occur at greater frequency and they carry sound waves faster.  Greater kinetic energy = less inertia = increased speed.
However, as sound waves are compressional waves traveling through a compressible medium, their speed depends not just on inertia of the medium, but also on its elasticity.
Generally, the closer together molecules are, the faster they will carry sound waves.  Although distance between molecules tends to increase when a medium is heated, this is relatively less important to the speed of sound within a given medium than is the faster movement of the molecules.
A: We know that temprature and kinetic energy is directly proportional. When the temprature is increased the kinetic energy of air molecules increase and the molecules move more quickly. Due to which propagation of sound is done quickly, increasing the velocity. 
A: The higher temp. implies higher speed for the molecule, so it collide with the next molecule at a faster time even if they are far away from each. on the other hand, the lower temp. means lesser speed and so it can also collide with its close neighbor at a longer time. merci!
