can someone verify if this is true?
I assume that P(i) holds for i < n, but then I would believe that this means the conclusion should be 3^n-1 and not 3^n.
However, the correct answer given by my teacher says 3^n is correct.
Asked
Active
Viewed 91 times
0
-
please pick up mathjax to type maths on the site. Start by surrounding mathy objects with dollar signs – Siong Thye Goh Jan 07 '19 at 11:56
-
1$f(n) = 1$ is also a solution. Just so you know. The given induction proof doesn't have base cases (and it can't, since we aren't given any base values for $f$), and therefore hasn't really proven that $f(n) = 3^n$ just yet. – Arthur Jan 07 '19 at 12:00
1 Answers
2
By assuming $P(i)$ holds for $i<n$, clearly, we have $f(n-1)=3^{n-1}$ from this assumption.
Our goal for the induction step is to argue that from properties $$P(i) \text{ holds for } i<n\tag{1}$$ and $$f(n)=4\cdot f(n-1)-3f(n-2)\tag{2},$$ we can conclude $P(i)$ holds for $i=n$, that is $f(n)=3^n$.
Siong Thye Goh
- 149,520
- 20
- 88
- 149