This paper presents an alternative approach for obtaining a converse Lyapunov theorem for discrete-time systems. The proposed approach is constructive, as it provides an explicit Lyapunov function. The developed converse theorem establishes existence of global Lyapunov functions for globally exponentially stable (GES) systems and for globally asymptotically stable systems, Lyapunov functions on a set [a,b] with 0<a<b< are derived. Furthermore, for specific classes of systems, the developed converse Lyapunov theorem can be used to establish non-conservatism of existence of a particular type of Lyapunov functions. Most notably, a proof that the existence of conewise linear Lyapunov functions is non-conservative for GES conewise linear systems is given and, as a by-product, tractable construction of polyhedral Lyapunov functions for linear systems is attained. © 2014 Elsevier B.V. All rights reserved.