I (independently) solved a fellow student's research problem. I want to publish it. What should I do?

There is a larger issue at hand that you seem to be missing.

Yes, I do believe that you can publish your own work, and probably independently if neither your advisor nor your colleague helped. And I understand that there are some field-dependent conventions in mathematics that would be best to discuss with your advisor.

That being said, I believe that, being a senior and more experienced student, you should not have allowed the situation to have reached this point. That is to say you should not have scooped your colleague in the first place. You offered your help to collaborate with your colleague and ended up quite literally stealing his project and are now thinking about publishing it because he was not able to work as fast or as efficiently as you (because he is inexperienced, as you said). This is something that should have been discussed with your advisor at a much earlier stage.

You should understand that this will probably not be the last time that you can benefit from collaboration, and you don't want to be known as the person who steals other people's projects. Healthy collaboration is an intrinsic part of academia (and society, in general). You are expected to be trusted to review other people's papers without scooping them, and in the future you will likely advise inexperienced students in their own projects, many of which have been suggested by you, and that you could solve with much less effort. More importantly, you will be partly responsible their success.

Speaking from your advisor's standpoint, I would consider your action harmful to the group's health. While I generally applaud collaboration between students, in my group, projects and milestones are set with the understanding that students can benefit from them, and that they can help them progress in their more ambitious goals (i.e., a dissertation). This is particularly important for inexperienced students. Should there be a major change of directions (such as a student unable to make progress and someone else benefiting from it), I would like it to be run through me (or other senior member of the lab) first so that it can be arranged for nobody to be in a losing situation. In your case, your colleague is in a losing situation, his name going in the paper or not.

The moment you noticed a solution to the problem, you should have informed your colleague (and possibly your advisor) and both of you should have worked on it, together.

Welcome to the wonderful world of academia! I appreciate your consideration of your fellow Ph.D. student. I would suggest to invite the student to do some work on the paper, and then have him as second author. Perhaps the student can work on that lower bound? Or write down why the other approach does not work? Or more simulations? You can probably come up with something. If he refuses, you can publish on your own. Either way, if the results are good you get a first author paper, and the other student gets something for his work.

I would run this by your advisor, he might have further advice.

My contribution to my first paper (which happened to be in applied mathematics) was a 15 minute hallway conversation with the other author. He put me down as a co-author, had me read drafts. I asked him why he put me in. "No one gets penalized for having collaborators, and I found our conversation enormously helpful." I've respected that guy ever since.

Don't sweat it, add him as a co-author, and move on. You received tremendous help from him, reward him with coauthorship. Writing the paper as a solo author, makes you looks selfish and greedy in this situation, for no real gain.