Found and corrected a mistake on someone's else paper -- praxis? 3-4 months ago I found a big mistake in a theorem's proof of a paper that had just been published (stats/cs community). I immediately notified the authors, who claimed to be aware of the mistake but admitted not knowing how to fix it.

This week I noticed that the authors didn't notify the community of the mistake (no updates on their arxiv paper, nothing on the author's websites, etc), even though the paper got a good visibility and already has quite a few citations. I went to check whether the mistake breaks the theorem, and found out that:

1 - the theorem statement is incorrect

2 - however, the statement holds under reasonable assumptions, but the proof requires a different technique (I have a full proof for that)

How should I proceed in this case? This theorem specifically is the main result of the paper, so I wouldn't be comfortable just sending them the corrected proof+statement and not getting properly recognized (e.g. only an acknowledgement). Should I write a short report on post it on arxiv? Send the proof under the requirement that I be added as a co-author? What is the praxis in this case?

EDIT:

Thanks for all the replies so far. I've contacted my advisor and have finished writing a short report (~4 pages) on the matter. I'm yet to decide whether I should contact the authors before posting the report, and whether a merger would be a good idea -- as some people said, it is a huge red flag that they admitted to be aware of the mistake and never took action, so I am not certain that I would like to be associated with the authors in a collaboration level.

1) The paper has already been published in a conference and its journal proceedings. I've contacted the authors after acceptance but before the proceedings were published, and they took no action.

2) The paper proposes a new algorithm B and states that it has the same running time as algorithm A, a classic method in the field, while having smaller memory cost and being easy to implement. The main theorem roughly states that T(B) = O(T(A)), which is wrong as for some inputs T(B) = infinity. The technical mistake is subtle and involves upper-bounding an infinite series, which in reality can diverge to infinity. I've ran the algorithm on a simple instance where it does not halt nor makes any progress.

3) It can be shown that, for some input distributions, T(B) = O(T(A)). The technical argument is a bit different from what they initially presented. Unfortunately, I think that for these distributions it can be shown that A has an even smaller memory cost than B, but I am not sure.
I have not been in such situation. However, I do not see what is the problem for you to write a paper complementing or correcting the previous paper? Isn't this how science works?

In my opinion, it is very toxic culture in academia to consider such thing as inappropriate. Those previous auathors are humans. Assuming good faith, that was what they knew and what was to the best of their knowledge, and to the best of the reviewers' knowledge, at the time of their publication. You got something, great, you have the right to get the credit for it. I feel it is unfair that you inform the authors offline. You should write it, and publish it too. 

Also, we should not forget that you might be wrong too! I do not mean to offend anyone. But if we remember that we are all humans and have limitations in our knowledge about exploring this world, we would take these issues in a more relaxed way.