I've got a math question on induction and I'm not sure how to solve it. Would anyone be able to give me some tips or do a step by step of how I'd be able to solve it?
The question goes as follows:
You are given $n$ envelopes, numbered $0$, $1$, $\ldots$, $n-1$. Envelope $0$ contains $2^0 = 1$ pound sterling, envelope $1$ contains $2^1 = 2$ pounds, envelope $2$ contains $2^2 = 4$ pounds, $\ldots$, and envelope $n − 1$ contains $2^{n−1}$ pounds. Let $P(n)$ be the assertion that: For all non negative integers $k < 2^n$, there is a subset of the $n$ envelopes whose contents total to exactly $k$ pounds. Prove by induction that $P(n)$ holds for all integers $n \geq 1$. Hint: Keep in mind that $2^{n−1} + 2^{n−1} = 2 \cdot 2^{n−1} = 2^n$ and consider three cases $k < 2^{n−1}$, $k = 2^{n−1}$, and $2^{n−1} < k < 2^n$ in the inductive step.
Anyone got any tips/advice on how to solve it? I had a look at how to do induction proof, and I found out that I need to do the base case ($n=1$), then suppose for $n=k$ and then prove for $n=k+1$, but the examples I looked at all had a formula, and this doesn't have one so I'm not sure how to do it or even how to get the base case.