We study superconductivity on the surface of a topological insulator, mediated by magnetic fluctuations in an adjacent ferromagnetic or antiferromagnetic insulator. Superconductivity can arise from effective interactions ...