It's completely commonplace to increase muscle mass while reducing body fat.
It's trivial to find 1000s of articles and papers on this, random examples https://health.usnews.com/wellness/fitness/articles/can-you-gain-muscle-while-losing-weight , https://www.healthline.com/nutrition/body-recomposition#how-it-works , https://www.verywellfit.com/mistakes-to-...
The solution of the apparent contradiction may be in the scales of time:
At any point in time, you can either slim down (catabolic, during excercise) or build muscle (anabolic, during rest after excercise), but
on a more coarse time scale where excercise and rest phases are "at the same time" both can happen "together".
See e.g. the ...
Yes. That's the normal state for beginners with more than enough body fat and no physical excercise.
Yes, different people get different tips on how to improve, it totally depends on your current physical state.
This even stands true even for older people, e.g. this study comes to the conclusion:
These results support the hypothesis that older persons who ...