-1
$\begingroup$

![enter image description here][1]

I have a problem to solve this recurrence. I tried by myself but it doesn't look understandable. Solve the following recurrence

$\endgroup$
  • $\begingroup$ Can you typeset your recurrence function in LaTeX? I don't realy understand what you mean right now. $\endgroup$ – Maarten Dhondt Mar 16 '14 at 14:12
  • 1
    $\begingroup$ You are right. With the current formatting the recurrence isn't understandable. From what I can extract, it looks like a straightforward induction on n should do the trick. $\endgroup$ – FrankW Mar 16 '14 at 14:16
  • 1
    $\begingroup$ What about matching opening braces with closing ones ? What does "*" mean here? This is unreadable. Why is the math in the title different from taht in the body of the question. I call it math, because I do not dare call it an equation. $\endgroup$ – babou Mar 16 '14 at 14:19
  • $\begingroup$ sorry guys there you have a picture now please help $\endgroup$ – Roben Mar 16 '14 at 14:22
  • 2
    $\begingroup$ A picture is not acceptable. Please use MathJax formatting, like Aryabhata did on your other question. Also, what did you try? What theorems have you studied in class, that you could use in your solution? $\endgroup$ – Gilles 'SO- stop being evil' Mar 16 '14 at 16:15
2
$\begingroup$

As FrankW mentioned, your question seems to be: Solve the recurrence

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

The solution $f(n) = 3n-1$ is already given. It just needs to proven:

  • base case: $f(1)=3-1=2$
  • otherwise: $f(n+1) = 3(n+1) - 1 = 3n + 3 - 1 = 3n - 1 + 3 = f(n) + 3$

Edit

As to your comment on how to find $f(n) = 3n-1$ (though it was given in the question), use induction on n:

  • $f(1) = 2$
  • $f(2) = 2+3 = 5$
  • $f(3) = 5+3 = 8$
  • $f(4) = 8+3 = 11$
  • $f(5) = 11+3 = 14$
  • $f(6) = 14+3 = 17$

So try to find a function for which $f(1) = 2, f(2) = 5, f(3) = 8, f(4) = 11, f(5) = 14, f(6) = 17,\ \dots$ Clearly it is $f(n) = 3n-1$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ it is prove the recurrence solution as you saw inn picture i dont understabnd did you get f(n)=3n−1. and is this all for prove $\endgroup$ – Roben Mar 16 '14 at 14:44
  • $\begingroup$ It's all there is to prove. The base case and the recurrence function. I didn't find the f(n)=3n-1, it was given in the question. $\endgroup$ – Maarten Dhondt Mar 16 '14 at 14:47
  • $\begingroup$ ok thank you very much i have starting now with recurrence and it looks complicated $\endgroup$ – Roben Mar 16 '14 at 14:49
  • $\begingroup$ I edited my post to show you how f(n)=3n-1 can be found when it's not given $\endgroup$ – Maarten Dhondt Mar 16 '14 at 14:56
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Mar 17 '14 at 16:00
2
$\begingroup$

Judging from the image, I think the exercise is trying to ask the following:

Given the recurrence $$f(n) = \begin{cases}2 & n=1\\f(n-1)+3 & n>1\end{cases},$$ show that $f(n) = 3n-1$.

Does this help?

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.