Note I said effort, not money.
It takes a certain amount of money and effort to evaluate the effectiveness of an ad channel. Most of the people I know who make money with PPC spent probably $1000, $2000 or more before they developed a campaign that really makes money.
When it comes to online ads it really is you spend $X to get $Y of revenue and if you don't get to a place where $Y>$X fast, it doesn't make sense to spend more.
It makes more sense to develop organic traffic and that comes through mechanisms like you befriend a fitness blogger and if he likes the app he blogs about it. Another logical thing is to make your own blog about fitness where you can work something about your app into the posts.
It takes a huge amount of time and effort to do the above but not a lot of money, but the results are a lot more enduring. If you do want to spend money on it, pay a PR agency or a writer, a "growth hacker" or somebody who can do that kind of work.