MHB How can I find the exact solution?

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion focuses on finding an exact solution for the recurrence relation S(m) = S(m^(1/r)) + 1, where m ≥ 2 and r > 1. The master theorem was initially applied, yielding S(m) = Θ(log_2(log_r m)), which was confirmed as correct. The participants then explored the substitution method to derive the exact solution, ultimately concluding that S(m) = log_r(log_2 m) is valid. Verification of the solution against the original recurrence was emphasized, ensuring that the derived solution satisfies the initial conditions. The conversation highlights the importance of confirming hypotheses in mathematical problem-solving.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

$$\text{ Find an asymptotic exact solution of the recurrence relation: } S(m)=S(m^{\frac{1}{r}})+1, m \geq 2, r>1,\text{ applying the master theorem.} \\ \text{ Then, find the exact solution of the recurrence relation, considering that } S(2)=0.$$

Applying the master theorem, I found that $S(m)=\Theta(\log_2{ \log_r m})$.
Am I right? (Thinking)

Then, I thought to find the exact solution, using the substitution method.
I found that $S(m)=S(m^{\frac{1}{r^k}})+k$.

The recursion ends, when $m^{\frac{1}{r^k}}=2 \Rightarrow k=\log_r{ \frac{1}{2}}$.

The $k$ I found is negative... :eek: but, it isn't possible that the level, at which the recursion ends is negative.. (Worried)

Have I done something wrong? (Thinking)
 
Physics news on Phys.org
evinda said:
Hello! (Wave)

$$\text{ Find an asymptotic exact solution of the recurrence relation: } S(m)=S(m^{\frac{1}{r}})+1, m \geq 2, r>1,\text{ applying the master theorem.} \\ \text{ Then, find the exact solution of the recurrence relation, considering that } S(2)=0.$$

Applying the master theorem, I found that $S(m)=\Theta(\log_2{ \log_r m})$.
Am I right? (Thinking)

Hey! (Happy)

It looks about right.
But how did you apply the master theorem?
The recurrence relation is not of the form $T (n) = aT (n/b) + f(n)$ is it? (Wondering)
The recursion ends, when $m^{\frac{1}{r^k}}=2 \Rightarrow k=\log_r{ \frac{1}{2}}$.

The $k$ I found is negative... :eek: but, it isn't possible that the level, at which the recursion ends is negative.. (Worried)

Have I done something wrong? (Thinking)

I think you did not solve for $k$ properly. (Worried)
 
I like Serena said:
Hey! (Happy)

It looks about right.
But how did you apply the master theorem?
The recurrence relation is not of the form $T (n) = aT (n/b) + f(n)$ is it? (Wondering)

That's what I did:

We set $n=\log_r m \Rightarrow r^n=m \Rightarrow m^{\frac{1}{r}}=r^{\frac{n}{r}}$.

Then, we have $S(r^n)=S(r^{\frac{n}{r}})+1$ and we set $R(n)=S(r^n)$.

So:

$$R(n)=R \left ( \frac{n}{r}\right)+1$$

Now, applying the master theorem, we get that: $f(n)=1=\Theta(n^{\log_b a}) \Rightarrow R(n)=\Theta(n^{\log_b a} \log_2 n)=\Theta(\log_2 n) \Rightarrow S(m)=\Theta(\log_2{\log_r n})$
I like Serena said:
I think you did not solve for $k$ properly. (Worried)

I tried it again and I got: $k=\log_r{\log_2 n}$.. Is it right now? (Thinking)
 
evinda said:
That's what I did:

We set $n=\log_r m \Rightarrow r^n=m \Rightarrow m^{\frac{1}{r}}=r^{\frac{n}{r}}$.

Then, we have $S(r^n)=S(r^{\frac{n}{r}})+1$ and we set $R(n)=S(r^n)$.

So:

$$R(n)=R \left ( \frac{n}{r}\right)+1$$

Now, applying the master theorem, we get that: $f(n)=1=\Theta(n^{\log_b a}) \Rightarrow R(n)=\Theta(n^{\log_b a} \log_2 n)=\Theta(\log_2 n) \Rightarrow S(m)=\Theta(\log_2{\log_r n})$

Nice! (Clapping)
I tried it again and I got: $k=\log_r{\log_2 n}$.. Is it right now? (Thinking)

Yep! (Nod)
 
I like Serena said:
Nice! (Clapping)

Yep! (Nod)

So, is the exact solution of the recurrence relation equal to $\log_r{\log_2 m}$ ? (Thinking)
 
evinda said:
So, is the exact solution of the recurrence relation equal to $\log_r{\log_2 m}$ ? (Thinking)

What do you get if you substitute that in the recurrence relation? (Wondering)
 
I like Serena said:
What do you get if you substitute that in the recurrence relation? (Wondering)

We get $\log_r{\log_2 m}=\log_r{\log_2{m^{\frac{1}{r}}}}+1=\log_r \left ( \frac{1}{r} \cdot \log_2 m\right)+1=\log_r{\log_2 m}$

So, it is right, yes? (Smile)
 
evinda said:
We get $\log_r{\log_2 m}=\log_r{\log_2{m^{\frac{1}{r}}}}+1=\log_r \left ( \frac{1}{r} \cdot \log_2 m\right)+1=\log_r{\log_2 m}$

So, it is right, yes? (Smile)

Yes! (Party)
 
I like Serena said:
Yes! (Party)

Great! (Party) Thanks a lot! (Smile)
 
  • #10
I like Serena said:
I think you did not solve for $k$ properly. (Worried)

Using the substitution method, do we find the exact solution and so we don't have to show that it is actually the solution, or do we just find a hypothesis of the solution? (Thinking)
 
  • #11
evinda said:
Using the substitution method, do we find the exact solution and so we don't have to show that it is actually the solution, or do we just find a hypothesis of the solution? (Thinking)

Generally speaking, you don't find the exact solution but only a hypothesis.
I wouldn't treat this case any other way. (Nerd)That is because a derivation is usually of the form: $P \Rightarrow Q \Rightarrow R$.
This means that $P$ and $R$ are not necessarily equivalent.
So you have to verify if $R$ is really the solution by testing it against $P$.

For instance, if you have $m^{1/r} = 1$, you can raise both sides to the power $r$ and get: $m=1^r = 1$ which is true for any $r$.
However, the original equation requires that $r\ne 0$. (Worried)
 
  • #12
I like Serena said:
Generally speaking, you don't find the exact solution but only a hypothesis.
I wouldn't treat this case any other way. (Nerd)That is because a derivation is usually of the form: $P \Rightarrow Q \Rightarrow R$.
This means that $P$ and $R$ are not necessarily equivalent.
So you have to verify if $R$ is really the solution by testing it against $P$.

For instance, if you have $m^{1/r} = 1$, you can raise both sides to the power $r$ and get: $m=1^r = 1$ which is true for any $r$.
However, the original equation requires that $r\ne 0$. (Worried)

So, you mean that we can use the substitution method, in order to find a hypothesis of the solution of the recurrence relation and then we have to verify it? If so, do we have to verify it, as we did in post #7 or do we have to do it in an other way? (Thinking)
 
  • #13
evinda said:
So, you mean that we can use the substitution method, in order to find a hypothesis of the solution of the recurrence relation and then we have to verify it? If so, do we have to verify it, as we did in post #7 or do we have to do it in an other way? (Thinking)

Yes, the way you did it in post #7 is a proper verification. (Nod)
It validates that all the solutions that you found are actual solutions.

In effect you verified that: $P \Rightarrow Q \Rightarrow R \Rightarrow P$.
Since the circle has been completed, we can tell that $P \iff R$.
 
  • #14
I like Serena said:
Yes, the way you did it in post #7 is a proper verification. (Nod)
It validates that all the solutions that you found are actual solutions.

In effect you verified that: $P \Rightarrow Q \Rightarrow R \Rightarrow P$.
Since the circle has been completed, we can tell that $P \iff R$.

A ok... (Nod)

In order to find the exact solution, we see that the recursion ends, when $m^{\frac{1}{r^k}}=2 \Rightarrow \lg{m^{\frac{1}{r^k}}}=1 \Rightarrow \frac{1}{r^k} \lg m=1 \Rightarrow r^k=\lg m \Rightarrow k=\log_r{\lg m}$

To get from the relation $r^k=\lg m$ to this one: $k=\log_r{\lg m}$, it must stand: $m \neq 1$. Do I have to write it? (Thinking)
 
  • #15
evinda said:
A ok... (Nod)

In order to find the exact solution, we see that the recursion ends, when $m^{\frac{1}{r^k}}=2 \Rightarrow \lg{m^{\frac{1}{r^k}}}=1 \Rightarrow \frac{1}{r^k} \lg m=1 \Rightarrow r^k=\lg m \Rightarrow k=\log_r{\lg m}$

To get from the relation $r^k=\lg m$ to this one: $k=\log_r{\lg m}$, it must stand: $m \neq 1$. Do I have to write it? (Thinking)

This is not necessary, since it is given that $m \ge 2$. (Wasntme)
 
  • #16
I like Serena said:
This is not necessary, since it is given that $m \ge 2$. (Wasntme)

Oh, yes... right! Thank you very much! (Smirk)
 

Similar threads

Back
Top