I thought I understood the principle of induction, but I must be missing something key about it if it inherently cannot be justified by evidence that it works.

The principle of induction is that which enables (probabilistic, not absolutely certain) inference of a general principle from observation of specific cases. It's what you use to infer that the sun is extremely likely to rise tomorrow, on the basis that it always has so far. More generally, it's the principle you use in any case where you're justifying some universal or general claim on the basis of a finite amount of specific evidence. This being the case, you cannot justify it with any finite amount of specific evidence, because you have a bootstrapping problem – you'd have to use it to justify itself.

If I already believed in the principle of induction, then I could start from the observation that in my experience it would have given the right answer far more often than not in cases where I already know what the answer turned out to be, and infer that I can therefore use it to build confidence in things I don't already know the answer to. But that inference is an exercise of the principle of induction, so I cannot make it until I've already been convinced that induction works – or simply accepted it as an axiom.