Skolem's problem: linear recurrences, decidability, and non-effective proofs

Suppose you are given a sequence {a_n} of integers which obeys a linear recurrence relation. Can you decide whether this sequence has a zero? It turns out that this problem is hard. I will attempt to explain why. There might be p-adic analysis, transcendental number theory, and/or finite automata.