I am attempting to solve some problems here. For exercise 1, the tightest result I could get is $4^k$. Is that the mininum possible bound?
I am trying to either find a tight example, or find a better estimate and I am failing at both tasks. If my proof might help with finding a tight example, I can post it (I still have not verified it very thoroughly though..).