1

What is the recursive definition of $f(n)=1+(-1)^n$ for $n≥1$? I think it's:

1) $f(1)=0$

2) $f(n)=f(n-1)+2$ if $n$ is even

$f(n)=f(n-1)-2$ if $n$ is odd

Is it correct?

Cameron Buie
  • 102,994
user560980
  • 71
  • Like with numbers and equations, a single number can satisfy many equations. For example, that sequence also satisfies an order-two homogeneous linear difference equation with constant coefficients (in particular no cases): $f(n+2)-f(n)=0, f(1)=0, f(2)=2$. (And many other equations too). –  May 20 '18 at 13:53
  • 1
    Also, if the type of recurrence relation is not restricted, then $f(n)=1+(-1)^n$ is already an order-zero, in-homogeneous, linear recurrence, with constant coefficients. –  May 20 '18 at 14:03

2 Answers2

1

Your casewise approach works. Alternatively, you can say $f(1)=0,$ and $$f(n)=f(n-1)-2(-1)^{n-1}$$ for $n\ge 2.$

To come up with that, I started with the explicit formula, so that $$f(n)-f(n-1)=\left(1+(-1)^n\right)-\left(1+(-1)^{n-1}\right),$$ then worked to get it into like terms to simplify: $$f(n)-f(n-1)=1+(-1)^n-1-(-1)^{n-1}$$ $$f(n)-f(n-1)=(-1)^n-(-1)^{n-1}$$ $$f(n)-f(n-1)=-2(-1)^{n-1}.$$

Just as simply, we could have noticed that $-(-1)^{n-1}=(-1)^n,$ leading instead to the formula $$f(n)=f(n-1)+2(-1)^n.$$

Cameron Buie
  • 102,994
  • Can I use this explicit formula ($f(n)-f(n-1)=...$) in every case? – user560980 May 20 '18 at 14:25
  • 1
    Well, if you have an explicit formula for $f(n),$ then, yes, $f(n)-f(n-1)$ will allow you to come up with a recursive formula. It may not always be the best one, though. For example, consider $g(n):=n!$ We could say that $g(1)=1,$ and use the above approach to find that $g(n)=g(n-1)+(n-1)!\cdot(n-1).$ However, a nicer formula could be found by finding $g(n)/g(n-1),$ instead, which would yield $g(n)=n\cdot g(n-1)$ as a recursive formula. – Cameron Buie May 20 '18 at 15:52
  • 1
    Better advice is to get a sense of pattern to how subsequent values are related, and try to find a nice way to express it. You and I both noticed that $2$ was alternately being added and subtracted. You expressed it casewise. I found ways to do it without cases. The other answerer found yet another way to do it without cases. – Cameron Buie May 20 '18 at 16:08
-1

$$f(1) = 0 \\ f(n) = 2 - f(n-1)$$

Kenny Lau
  • 25,049