In this paper we investigate stability analysis for discrete-time switched systems. We first consider quadratic Lyapunov functions defined over a nonminimal state encompassing the past history of the state trajectory over a finite horizon. This allows us to state necessary and sufficient conditions for testing uniform exponential stability. Quite remarkably, such conditions can be recast into suitable Linear Matrix Inequalities (LMIs). Next, we consider more general Lyapunov functions dependent also on the past of the switch trajectory. We show that, despite the increased flexibility, this class is no more powerful in capturing stability than the previous class of quadratic Lyapunov functions. However, the associated LMI-based tests may be computationally more advantageous than the ones derived in the quadratic case.