[waldrews]

No invertible function can map every non-negative integer to a lower or equal non-negative integer (no perfect compression), but you can have functions that compress everything we care about at the cost of increasing the size of things we don't care about. So the recursive de-indexing strategy has to sometimes fail and increase the cost (once you account for storing the prefix).

[psychoslave]

Is there some inductive proof of that? Or is that some conjuncture?

Actually any resources related to that point could be fun to explore

[waldrews]

It's a classic application of the pigeonhole principle, the first on in this list:

https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...