We develop a new method for pricing options on discretely sampled arithmetic average in exponential Lévy models. The main idea is the reduction to a backward induction procedure for the difference Wn between the Asian option with averaging over n sampling periods and the price of the European option with maturity one period. This allows for an efficient truncation of the state space. At each step of backward induction, Wn is calculated accurately and fast using a piece-wise interpolation or splines, fast convolution and either flat iFT and (refined) iFFT or the parabolic iFT. Numerical results demonstrate the advantages of the method.