Recurring Equations: Solving for T(n) with Mathematical Induction

  • Thread starter Thread starter XodoX
  • Start date Start date
  • Tags Tags
    Recurrence
Click For Summary

Homework Help Overview

The discussion revolves around solving a recurrence relation T(n) = T(n/7) + T(4n/5) + n for n > 35, with a specified base case for n ≤ 35. Participants are exploring the implications of the recurrence and the conditions under which it is defined.

Discussion Character

  • Exploratory, Assumption checking, Problem interpretation

Approaches and Questions Raised

  • Participants are questioning the completeness of the recurrence relation, particularly regarding missing elements and the handling of non-multiples in the equations. There is also uncertainty about the application of mathematical induction in this context.

Discussion Status

The discussion is ongoing, with participants seeking clarification on the recurrence setup and the implications of the base case. Some have offered suggestions for interpreting the problem, while others express confusion about the mathematical operations involved.

Contextual Notes

There is a noted lack of additional context surrounding the problem, which may affect how participants approach the solution. The discussion includes concerns about the validity of certain calculations and the handling of specific cases within the recurrence.

XodoX
Messages
195
Reaction score
0

Homework Statement



Solve the recurrence: T(n) = T(n/7) + T(4n/5) + n for n > 35 with base case T(n) = constant for n ≤ 35.

Homework Equations


The Attempt at a Solution



Is this mathematical induction? No idea how to do this one.
 
Last edited:
Physics news on Phys.org
You seem to be missing a "=". Where is it supposed to be?
 
Hi XodoX, it does look like a recurrence, except, as HallsofIvy is pointing, the recurrence rule is missing.
Is this T(n+1)=T(n)+T(n/7)+T(4n/5)+n ? (T(36)=3c+35)
if it is, what when n is not a multiple of 7 and 4n is not a multiple of 4 ? we take the floor / ceiling ? do you have some context around this question ?

Cheers...
 
Fixed it. Sorry, wrong button.
 
Still, is 36/7=5 ? is 144/5=28 ?
just to make sure we are solving the right problem, do you have some context around this puzzle ?

Cheers...
 
No, nothing else. So plug in numbers? But the equation does not hold up. I don't get it.
 
Last edited:

Similar threads

Proving that a recurrence holds for all n
  • · Replies 11 ·
Replies
11
Views
2K
Avoid unpleasant integrals in solving IVP
  • · Replies 3 ·
Replies
3
Views
2K
How to find upper bound for recurrence relation
  • · Replies 1 ·
Replies
1
Views
2K
Proof by Induction of String exponentiation? (Algorithms)
  • · Replies 5 ·
Replies
5
Views
2K
Frequencies for harmonic oscillator with multiple periodic solutions?
  • · Replies 6 ·
Replies
6
Views
1K
Where is the recurrence stable in the (n,x) plane for increasing n?
  • · Replies 2 ·
Replies
2
Views
1K
Prove this inequality using induction
  • · Replies 2 ·
Replies
2
Views
2K
Solve the recurrence relation using iteration
  • · Replies 7 ·
Replies
7
Views
2K
Given unit impulse response, obtain differential equation
  • · Replies 7 ·
Replies
7
Views
2K
How to convince myself that I can take n=1 here?
  • · Replies 1 ·
Replies
1
Views
1K