Tom Bombadil and Luthien Tinuviel

[Eldy]

Originally Posted by Huinesoron

But can it really be a coincidence that Tolkien wrote their magic as so similar to each other?

Yes, in that I don't think there's any particular connection between the two, but no in that I think the reason they are similar is because that's how "magic" often works in Arda. As you point out, being able to know things despite distance in time and/or space is a common trait insofar as mystical abilities are concerned, not just for Bombadil and Tinuviel. Power expressed through song is likewise a common motif. Besides the fact that the universe itself was created through song, we see (for example) that Felagund "strove with Sauron in songs of power" while imprisoned on Tol-in-Gaurhoth (TS, Of Beren and Lúthien), in LOTR Gandalf "softly sang" just before unveiling himself with magical theatrics like rolling thunder and blotting out the sunlight (TTT, III 6), and Sam invoked the powers of the Phial of Galadriel by singing a portion of A Elbereth Gilthoniel, the words of which came to him despite not knowing Sindarin (TTT, IV 10).

That's my take, anyway.