DAPC19-062.Deceptive Dice

Recently your town has been infested by swindlers who convince unknowing tourists to play a simple dice game with them for money. The game works as follows: given is an $n$-sided die, whose sides have $1, 2, \ldots, n$ pips, and a positive integer $k$. You then roll the die, and then have to make a choice. Option 1 is to stop rolling. Option 2 is to reroll the die, with the limitation that the die can only be rolled $k$ times in total. Your score is the number of pips showing on your final roll.

Obviously the swindlers are better at this game than the tourists are. You, proud supporter of the Battle Against Probabilistic Catastrophes, decide to fight this problem not by banning the swindlers but by arming the tourists with information.

You create pamphlets on which tourists can find the maximum expected score for many values of $n$ and $k$. You are sure that the swindlers will soon stop their swindling if the tourists are better prepared than they are!

The layout of the flyers is done, and you have distribution channels set up. All that is left to do is to calculate the numbers to put on the pamphlet.

Given the number of sides of the die and the number of times you are allowed to roll, calculate the expected (that is, average) score when the game is played optimally.