Proof with recursion and logarithms

[enigmatic01]

Homework Statement

Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30 instructions for all n ≥ 1.

lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a) - lg(b) for any non-zero a,b

Relevant Equations

...

Homework Statement: Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30 instructions for all n ≥ 1.

lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a) - lg(b) for any non-zero a,b
Homework Equations: ...

This is how far I get:

let n = k+1

instructions for f(k+1) = 10(k+1) + 30 + 10(k+1)/2 + 30 + 10(k+1)/2 + 30
= 10k + 10 + 30 + (10k+10)/2 + 30 + (10k+10)/2 + 30
= 10k + 10 + 30 + 10k + 10 + 30 + 30
then rearranging we get = (10k + 30) + (10K + 30) + 10 + 10 + 30
from inductive step we know (10k + 30) = (10k⋅lgk + 32k - 30) therefore
= (10k⋅lgk + 32k - 30) + (10k⋅lgk + 32k - 30) + 10 + 10 + 30

I get stuck at this point

 

[tnich]

I think proof by induction will work, but you will need to figure out the right induction hypothesis. Specifically, you will need to show what the value of $f(n)$ is in step $k+1$ given that you know $f(n/2)$ in step $k$. How would you express $n_k$ for $k\in \mathbb Z^+$?

By the way, the problem statement is incomplete in that it does not tell you what happens when $n/2$ in not an integer. The number of instructions in the case is undefined. Is there a definition that is consistent with the desired result?

 

[enigmatic01]

I think proof by induction will work, but you will need to figure out the right induction hypothesis. Specifically, you will need to show what the value of $f(n)$ is in step $k+1$ given that you know $f(n/2)$ in step $k$. How would you express $n_k$ for $k\in \mathbb Z^+$?

By the way, the problem statement is incomplete in that it does not tell you what happens when $n/2$ in not an integer. The number of instructions in the case is undefined. Is there a definition that is consistent with the desired result?

Unfortunately it makes no mention what happens when n/2 is not an integer. Which is confusing me because the first sentence of the problem states that f(n) "accepts an integer n as a parameter" yet it has 2 recursive calls of n/2.

 

[Mark44]

Unfortunately it makes no mention what happens when n/2 is not an integer. Which is confusing me because the first sentence of the problem states that f(n) "accepts an integer n as a parameter" yet it has 2 recursive calls of n/2.

My sense is that this is a "computer sciencey" type question. If so, one might interpret n/2 to mean integer division -- i.e., the result is an integer. For example, 4/2 == 2, but also 5/2 == 2 when integer division is used.

 

[enigmatic01]

My sense is that this is a "computer sciencey" type question. If so, one might interpret n/2 to mean integer division -- i.e., the result is an integer. For example, 4/2 == 2, but also 5/2 == 2 when integer division is used.

I sent an e-mail to my TA I'm waiting for a response. Also, I apologize if this is not considered the correct forum I was stuck between this one and the Engineering forum.

 

[Mark44]

Also, I apologize if this is not considered the correct forum I was stuck between this one and the Engineering forum.

Not a problem -- I moved your thread for you, assuming that this is more of a computer science question.

Before attempting an induction proof, as was earlier suggested, what I would do is make a small table of instruction counts for n = 2, n = 3, n = 4, to see if you can see a pattern developing.

 

[tnich]

Unfortunately it makes no mention what happens when n/2 is not an integer. Which is confusing me because the first sentence of the problem states that f(n) "accepts an integer n as a parameter" yet it has 2 recursive calls of n/2.

I have tried the given formula and found that it works for $n$ a power of 2.

As @Mark44 says, this is a computer science question, so you might think of the given formula as a big O complexity bound, define $f(n) = 0$ for odd $n>1$ or as @Mark44 suggests, use integer division, and go from there.

I think you still need to build your proof by induction so that the induction step looks like:

"$f(n) = 10n \log_2 n +32n-30$ implies that $f(2n) = 10(2n) \log_2 (2n) +32(2n)-30$. "

What function of $k\in \mathbb Z^+$ could you substitute for $n$ to make this look like the standard induction step?

 

[enigmatic01]

I have tried the given formula and found that it works for $n$ a power of 2.

As @Mark44 says, this is a computer science question, so you might think of the given formula as a big O complexity bound, define $f(n) = 0$ for odd $n>1$ or as @Mark44 suggests, use integer division, and go from there.

I think you still need to build your proof by induction so that the induction step looks like:

"$f(n) = 10n \log_2 n +32n-30$ implies that $f(2n) = 10(2n) \log_2 (2n) +32(2n)-30$. "
ƒ
What function of $k\in \mathbb Z^+$ could you substitute for $n$ to make this look like the standard induction step?

Thank you for your help. Do you mean setting n = k + 1 then substituting that into the f(2n) equation?

 

[enigmatic01]

If anyone cares I figured it out (with help)...

After proving base case of f(1) we assume function holds true for all n up to k (strong induction). Consider k+1.

f(k+1) = 10(k+1) + 30 + 2*f( (k+1) /2) since k is > 1 we know (k+1)/2 is less than k

= 10(k+1) + 30 + 2[ 10( (k+1) /2 )*lg( (k+1) / 2) + 32( (k+1) / 2) - 30 ]

after skipping some algebra...

= 10(k + 1) [ 1 + lg( (k + 1) / 2) ] + 32(k + 1) - 30

= 10(k + 1) [ 1 + lg(k + 1) - lg(2) ] + 32(k + 1) - 30

= 10(k + 1)[1+ lg(k + 1) - 1 ] + 32(k + 1) - 30

= 10(k + 1)lg(k + 1) + 32(k + 1) - 30

 

[tnich]

If anyone cares I figured it out (with help)...

After proving base case of f(1) we assume function holds true for all n up to k (strong induction). Consider k+1.

f(k+1) = 10(k+1) + 30 + 2*f( (k+1) /2) since k is > 1 we know (k+1)/2 is less than k

= 10(k+1) + 30 + 2[ 10( (k+1) /2 )*lg( (k+1) / 2) + 32( (k+1) / 2) - 30 ]

after skipping some algebra...

= 10(k + 1) [ 1 + lg( (k + 1) / 2) ] + 32(k + 1) - 30

= 10(k + 1) [ 1 + lg(k + 1) - lg(2) ] + 32(k + 1) - 30

= 10(k + 1)[1+ lg(k + 1) - 1 ] + 32(k + 1) - 30

= 10(k + 1)lg(k + 1) + 32(k + 1) - 30

There is a hidden assumption in your proof - that $f(n)$ is defined for $n$ not an integer. Aside from that it works, but if I were grading your homework, I would take some points off for that. However, I would give you some credit if you showed that you at least knew you were making that assumption, for example, if you stated what you assumed to be the number of operations when $n$ is not an integer.

Still, I think the issue is really in the problem statement, since as stated it is not true except for $n$ a power of 2.

 

[enigmatic01]

There is a hidden assumption in your proof - that $f(n)$ is defined for $n$ not an integer. Aside from that it works, but if I were grading your homework, I would take some points off for that. However, I would give you some credit if you showed that you at least knew you were making that assumption, for example, if you stated what you assumed to be the number of operations when $n$ is not an integer.

Still, I think the issue is really in the problem statement, since as stated it is not true except for $n$ a power of 2.

I sent an e-mail to my TA for clarification but I have not heard back yet. Any suggestions on how I should address it if I don't hear back?

 

[tnich]

I sent an e-mail to my TA for clarification but I have not heard back yet. Any suggestions on how I should address it if I don't hear back?

You could give a counter example that shows the formula does not work. Show that the number of operations for $n=3$ is undefined.

Then you could give your proof and explain what you would have to assume about the number of operations for $f(n)$ when $n$ is not an integer to make the proof work. Is it zero? Is it $10n + 30$? Is it $10n + 30 + 2[\text {number of operations for } f(n/2)]$? Is it $10n \,lg\,n + 32n -30$?

One question: did you state the problem in the original post exactly as it was given to you, or did you paraphrase it?