Question

Solve the following recurrence:
\[f(x) =\begin{cases} x & x \le 3 \\ f(x-3) + 4 & x > 3\end{cases}\]

Answer 1

Attempt:
if x ≡ 0 (mod 3)
f(x) = f(x-3) + 4 = f(x-6) + 8 = ... = f(x-3i) + 4i = ...
= f(x - 3 (x/3 - 1)) + 4(n/3 - 1) = 4n/3 - 1

if x ≡ 1 (mod 3)
f(x) = f(x-3) + 4 = f(x-6) + 8 = ... = f(x-3i) + 4i = ...
\(= f(x - 3 (\lfloor{\frac{x}{3}}\rfloor )) + 4 (\lfloor{\frac{x}{3}}\rfloor)= f(1)+4(\lfloor{\frac{x}{3}}\rfloor) = 4(\lfloor{\frac{x}{3}}\rfloor ) + 1\)

if x ≡ 3 (mod 3)
f(x) = f(x-3) + 4 = f(x-6) + 8 = ... = f(x-3i) + 4i = ...
\(= f(x - 3 (\lfloor{\frac{x}{3}}\rfloor )) + 4 (\lfloor{\frac{x}{3}}\rfloor)=f(2) + 4 (\lfloor{\frac{x}{3}}\rfloor)=4(\lfloor{\frac{x}{3}}\rfloor ) + 2\)


This is the best I can do :(

Answer 2

Hmmm, start with \[
\begin{split}
f(x) &= f(x-3) +4 \\
&= (f(x-3-3) + 4) + 4 = f(x-2(3)) + 2(4) \\
&= f(x-3n) +4n
\end{split}
\]

Answer 3

Then we need to solve for \(n\) in: \[
x-3n \leq 3
\]

Answer 4

\[x-3 \le 3n\]\[n\ge\frac{x-3}{3}\]

Answer 5

But why do we need to solve for n in x−3n≤3 ?

Answer 6

So that we can let \(f(x-3n) = x\)

Answer 7

Now we need to find \(n=g(x)\) and substitute it in.

Answer 8

Also, \(n\) has to be an integer as well.

Answer 9

What is n=g(x)?

Answer 10

The point is that there is some expression for \(x\) that will allow us to replace \(n\) with an expression of \(x\).

Answer 11

\[n=\lfloor\frac{x}{3}\rfloor-1\]
?

Answer 12

So far we have: \[
f(x) =\begin{cases}
x &x\leq 3\\
(x-3n)+4n&x>3
\end{cases}
\]

Answer 13

The best way is to just test values of \(x\) such as \(4,5,6,7\).

Answer 14

\[
\begin{array}{ccccc}
x&4&5&6&7\\
n&1&1&1&2
\end{array}
\]

Answer 15

Looks like \(n = \lfloor \frac{x-1}{3} \rfloor\)

Answer 16

\[
(x−3n)+4n = x-\left\lfloor \frac{x-1}{3} \right\rfloor
\]

Answer 17

\[
n=\left\lfloor \frac{x-1}{3}\right\rfloor \implies n\leq \frac{x-1}{3} < n+1
\]

Answer 18

How do you get that (x-1)/3?

Answer 19

If you can somehow get this inequality theoretically, can you can do this problem more theoretically without using test points.

Answer 20

I started with \(x/3\), but since \(6/3=2\) that means we need to make \(x\) smaller. So I did \((x-1)/3\) and since \((6-1)/3 = 5/3 = 1+2/3\), I knew I needed to floor it to get just \(1\).

Answer 21

Why are you doing that?

Answer 22

Then I tested this on 7. \((7-1)/3= 2\). Then I tested it on \(4\).

Answer 23

Rather than "make \(x\) smaller" I should say, "make the numerator smaller".

Answer 24

http://www.wolframalpha.com/input/?i=Table%5Bn+%2B+Ceiling%5B%28n+-+3%2B0.001%29%2F3%5D+%2C+%7Bn%2C+0%2C+10%7D%5D

Answer 25

Here is a display of what I got:
http://www.wolframalpha.com/input/?i=Table%5BFloor%5B%28n+-+1%29%2F3%5D+%2C+%7Bn%2C+3%2C+10%7D%5D

Answer 26

Actually, what is going on here...

Answer 27

Remember that \(n\) just represents the number of times we invoked recursion.

Answer 28

looks like putting 0.001 to adjust value at zero was bad idea.

Answer 29

@RolyPoly ceil(x/3)-1 = floor((x-1)/3)

Answer 30

works for non negative values
http://www.wolframalpha.com/input/?i=Table%5Bn+%2B+Ceiling%5B%28n+-+3%29%2F3%5D+%2C+%7Bn%2C+1%2C+10%7D%5D

Answer 31

What's the point of putting up WolframAlpha link without explanation?

Answer 32

@experimentX What are you trying to get?

Answer 33

the general formula for $f(x)$ in terms of $x$

Answer 34

@RolyPoly, where are you confused?

Answer 35

starting from the inequality
x−3≤3n
n≥(x−3)/3

n=ceil((x-3)/3)=ceil(x/3)-1
or n=floor((x-3)/3+2/3)=floor((x-1)/3)
2/3 is added to convert from ceil to floor

Answer 36

Hmm, I guess we should also test \(3.5\) and \(6.5\)

Answer 37

in general, ceil(x/k)=floor(x/k+(k-1)/k)
and floor(x/k)=ceil(x/k-(k-1)/k)

Answer 38

\[f(x)=f(x−3)+4 = f(x−3n)+4n = x-3n + 4n = x+n\]
Take \(n=\lceil\frac{x}{3}\rceil-1\), the function becomes
\[f(x) = x+\lceil\frac{x}{3}\rceil-1\]
To test if it is correct:
Using the given recurrence equation:
x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
f(x) | 1 | 2 | 3 | 5 | 6 | 7 | 9 | 10 | 11

Using the equation I got:
x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
f(x) | 1 | 2 | 3 | 5 | 6 | 7 | 9 | 10 | 11

Looks good.

Answer 39

blows up at zero lol

Answer 40

Ehmmmmm

Answer 41

Never mind, where x is a positive integer. :P

Answer 42

ok ok

Answer 43

To confirm again why we are using ceiling instead of floor function here:
\(x-3n \le 3\)
The left actually gives us what the base case would be, either 1, 2, or 3.
Solving for n:
\(x-3n \le 3\)
\(x-3 \le 3n\)
\(n\ge \frac{x-3}{3}\)
Since n is an non-negative integer, we need either ceiling or floor function here.
If we use floor function, when x=4, we get \(n = \lfloor \frac{4-3}{3}\rfloor = 0 \), but n should be grater \(\frac{4-3}{3}\), i.e. \(\frac{1}{3}\), so, we cannot use ceiling function here, right?

Answer 44

yup; the ceiling function finds an integer greater than or equal to x; the floor function, an integer less than or equal to x

Answer 45

A type again. It should be
"so, we cannot use floor function here, right?"

Answer 46

just add +1 after using floor function ... it's the same thing lol

Answer 47

Okay, how about this: \[
x-3n\leq 3\\
x\leq 3n+3\\
\frac x3 \leq n+1

\]If we add a restriction \(n<x/3\) then\[

n<\frac x3 \leq n+1\\
n-1<\frac x3 -1 \leq n \implies n=\left\lceil\frac{x}{3}-1\right\rceil = \left\lceil\frac{x}{3}\right\rceil -1
\]

Answer 48

How to you get ceiling function from that inequality?

Answer 49

From definitions. \[
n = \lfloor x \rfloor \implies n\leq x<n+1\\
n = \lceil x \rceil \implies n-1 < x \leq n
\]

Answer 50

Should say \(\iff\).

Answer 51

Ok...
But why do we add the restriction n<x/3?

Answer 52

Think about it. If \(7=\lceil x\rceil \) then \(6<x\leq 7\)

Answer 53

We can add any arbitrary restriction we want so long as it never contradicts existing restrictions.

Answer 54

Actually, let me think give a better justification.

Answer 55

Remember that \(n\) is just the number of times we will invoke recursion.

Answer 56

Hmmm, ok... Wait! Are you going to write an recursive function for n? :O

Answer 57

No, I am not.

Answer 58

Since \[
\frac x3\leq n+1
\]give us a lower bound for \(n\), how would you suppose we find an upper bound?

Answer 59

That is, what do we know to be the maximum number of times that we would invoke recursion?

Answer 60

To be honest, I added \(n<x/3\) by design.

Answer 61

However, we know we want the smallest \(n\) that satisfies the equation: \[
\frac x3\leq n+1
\]

Answer 62

The restriction \(n < x/3\) exists so that we don't get multiple integer solutions for \(n\).

Answer 63

Why?

Answer 64

Why do we want the smallest \(n\)?
Why what?

Answer 65

Why does the existence of the restriction n<x/3 prevent us from getting multiple integer solutions for n?

Answer 66

Because if \(n<x/3\leq n+1\) then, that means \(x/3\in (n,n+1]\). The only integer in this interval is \(n+1\). We know \(n\) is not in it. We know \(n+2\) is not in it.

Answer 67

Why do we not want a multiple integer solutions for n?

Answer 68

If we have multiple solutions for \(n\), then the larger ones will have us invoke recursion when we should be sticking with our base case.

Answer 69

x/3≤n+1 <=> x/3 - 1 ≤ n
Is x/3 -1 the lower bound of n?

Answer 70

Yes. The other bound is the fact that \(n\) is an integer.

Answer 71

Okay, here is an idea...

Answer 72

We said \(x-3n\leq 3\) is important, because it will tell us when \(n\) is large enough to give us the base case.

Let's consider the value \(x-3m> 3\) to find out where \(m\) is small enough to require recursion. This just gives us \(x/3>m+1\).

If we add one more recursion to \(m\), it should put us into the base case.
That means \(n=m+1\). Putting it into our equation of \(m\) gives \(x/3>n\).

Answer 73

Basically:
We need \(n\) or more recursions to get to the base case.
We need \(m\) or less recursions to stay out of the base case.
We know that \(n>m\). We also know \(n-m>0\) and \(n-m\) is an integer.

For \(n\) and \(m\) to be closest together, we minimize \(|n-m|=n-m\).
The next integer following \(0\) is \(1\).

If \(n-m=1\), then \(n=m+1\).

Answer 74

Why do we need to minimize |n-m| ?

Answer 75

That means \(n\) and \(m\) are closest together. Remember that \(|n-m|\) is just the distance between the two.

Answer 76

What is the significance of finding the condition where they are closest together though?