Find f(n) in terms of a and n if:?

Question

f(n)=f(n-1)+a^n and f(1)=1for every n of N

Answer 1

f(n) = f(n - 1) + a^n
= f(n - 2) + a^(n - 1) + a^n
= f(n - 3) + a^(n - 2) + a^(n - 1) + a^n
.
.
f(n) = f(2) + a^1 + a^2 + a^3 + .... + a^n
f(n) = 1 + a^1 + ... + a^n

This is a geometric series, with a1 = 1 and r = a. Therefore, our closed form expression is

f(n) = a1 [1 - r^(n + 1)] / (1 - r).
Substituting a1 = 1 and r = a, we have

f(n) = [1 - a^(n + 1)] / [1 - a]


***
Let's verify this by induction.

Prove that, for the recurrence f(n) = f(n - 1) and f(1) = 1, that
f(n) = [1 - a^(n + 1)] / [1 - a]

Base case: Let n = 1. Then f(1) = 1 [by definition of the recurrence], and
f(1) = [1 - a^(1 + 1)] / [1 - a] = [1 - a] / [1 - a] = 1, so the formula holds true for n = 1.

General case: Assume the formula holds true for n = k. That is, assume that
f(k) = [1 - a^(k + 1)] / [1 - a]

{We want to prove that f(k + 1) = [1 - a^(k+1+1)] / [1 - a] }
But, what does f(k + 1) equal?

f(k + 1) = f(k) + a^(k + 1) {by definition of the recurrence.

f(k + 1) = ([1 - a^(k + 1)] / [1 - a]) + a^(k + 1) {by our induction hypothesis}

f(k + 1) = ([1 - a^(k + 1)] / [1 - a]) + (1 - a)a^(k + 1) / [1 - a]

= { [1 - a^(k + 1)] + (1 - a)a^(k + 1) } / [1 - a]
= ( 1 - a^(k + 1) + a^(k + 1) - a*a^(k + 1) ) / (1 - a)
= (1 - a^(k + 2)) / (1 - a)
= (1 - a^(k + 1 + 1) / (1 - a)

Therefore the formula holds true for n = k + 1. Thus, by the principal of mathematical induction, for the recurrence
f(n) = f(n - 1) + a^n and f(1) = 1, it follows that
f(n) = [1 - a^(n + 1)] / [1 - a] for all natural numbers n.

Answer 2

f(1)=1 so
f(2)= f(1) + a^2 = 1 +a^2
f(3)=f(2)+a^3 = 1+a^2 +a^3
f(4)=f(3)+a^4 = 1+a^2+a^3+a^4
SO f(n)= 1+a^2+a^3+...+a^n