How to make this cool Audio Spectrum Visualizer
Is there a mathematical relation between n and Fs ?)


$n$ will determine your frequency resolution. For example, if $f_s = 16kHz$ and $2^n = 8192$, each bin in your FFT will have a width of about $16000 / 8192 \sim 2$ Hz. From your image, it looks like the smallest FFT bin width you want is 10 Hz wide. This means that if $f_s = 16kHz$, you can work with a size as low as $2^n = 2048$, but no smaller.


  One other thing that I want to know is "Can a Arduino do this fft in
  real time @ 8Khz sampling"?


There are many types of Arduino boards. This is absolutely doable with the recent boards that have 32-bit ARM processors. On the older 8-bit AVR-based Arduino boards, the data point I found is that a size 256 FFT runs in 7ms. So it would still be possible with some corner cutting, such as:


Reducing the sample-rate to 8kHz as you suggest, and get a few less bars in the upper range (or faking the data - there's not much going on in here which is not correlated with the few bars before it anyway...)
Reducing the FFT size and get a few less bars in the lower range
Reducing the frame rate at which you do the analysis, and if necessary use some interpolation between frames.


I'm pretty sure I've already seen a bunch of projects doing that. If you only need a few bars, another approach is to use a filter bank.