1. ## Cannot get my head around these functions - guidance needed please

Hi everyone, I'm normally ok with algebra, functions and the like but this question was posed in a clicker question in class and I don't know how to approach answering it.

The following functions produce the same answer, true or false?
f(n) = if n=0 then 1, else n + f(n-1)
g(n) = n(n+1)/2

As I have stated, this question formed part of a clicker question is class - but I would like to know the steps to solving it should something similar pop up again. The question takes a max of 3 mins to answer (clicker question limit) so I don't imagine a long rambling solution is required. As I say, any steps in solving this bad boy would be appreciated.

2. ## Re: Cannot get my head around these functions - guidance needed please

g(0) = 0, but f(0) = 1, so these are different functions.

On the other hand, if we had

$f(n)=\begin{cases}0&n=0\\n+f(n-1)&n>0\end{cases}$

then

\begin{align*}f(n)&=n+f(n-1)\\&=n+(n-1)+f(n-2)\\&\hspace{1cm}\dots\\&=n+(n-1)+\dots+1+f(0)\\&=n+(n-1)+\dots+1\\&=n(n+1)/2\\&=g(n)\end{align*}

The second last equality is the sum of an arithmetic progression.

3. ## Re: Cannot get my head around these functions - guidance needed please

Did it not ever occur to you to actually evaluate g(0)?