1. The problem statement, all variables and given/known data Solve the recurrence relation (use iteration). an = an-1 + 1 + 2n-1 a0 = 0 Then prove the solution by mathematical induction. 2. Relevant equations 3. The attempt at a solution a1 = 2 a2 = 5 a3 = 10 a4 = 19 a5 = 36 The solution appears to be an = n + 2n - 1 How are we supposed to get that though? I just guessed and did trial and error. That's really the only/primary way? Also, what are the properties of this recurrence relation (e.g., linear, homogeneous, etc.)? Why? Also sorry if this is posted in the wrong section, I didn't know where it belongs if not here. So how do I prove (or disprove, since I've only tried it out for so many of these) my solution using induction? Thank you so much.