Recurrences

An easy recurrence

Consider the following recursive function:

f$($n$)=\{13$f$($n$1)+5$if$$n$=0$if$$n$1$

Prove that f$($n$)=12(73$n$5)$ for all n$0.$

A wild recurrence

Consider the following recursive function:

f$($n$)=014$f$($n$2)$if$$n$=0$if$$n$=1$if$$n$2$

Prove that f$($n$)=2$n$2((1)$n$+1+1)$ for all n$0.$

Breaking bad

Consider the following recursive function:

f$($n$)=\{1$max$\{$f$()+$f$($n$)$:$$ in $\{1,...,$n$1\}\}$if$$n$=1$if$$n$2$

Give a closed form solution for f$($n$)$ and then prove that your closed form solution is correct.