Can someone give me an example of a challenging proof by induction? I'm about to give my first consultation and the topic is proof by induction. The students are new to calculus and I assume they don't know anything besides precalculus. Can anyone give me a proof by induction which is a bit different, challenging, maybe foreshadows other areas of calculus (derivation or whatever) because the prof who teaches them as well already have shown them a lot of easy ones. I'm glad even if you can give an example where it is hard to see that it can be proved by induction.

Prove that, for all positive integers $n$, there exists a partition of the set of positive integers $k\leq 2^{n+1}$ into sets $A$ and $B$ such that
$$\sum_{x\in A} x^i = \sum_{x\in B} x^i$$
for all integers $0\leq i\leq n$.
