MHB What are the next steps after finding a pattern in iterative substitution?

AI Thread Summary
After identifying a pattern in the iterative substitution for the equation T(n)=2T(n/2)+n^2, the next step is to express the general form of the pattern derived from the iterative process. This involves applying the definition of T multiple times to establish a formula. Additionally, one can derive an explicit formula for T when n is a power of 2, using a specific base case such as T(1). Proving this formula through mathematical induction is also recommended to validate the findings. Conclusively, these steps help solidify understanding and provide a clear solution to the recurrence relation.
fvnn
Messages
2
Reaction score
0
Hi i Have this equation:
[M]T(n)=2T(n/2)+n^2[/M]


I understand for iterative substitution you need to find patterns so here's what i got:
[M]2^2T(n/2^2)+n2/2+n^2
2^3T(n/2^3)+n2/2^2+n2/2+n^2[/M]

My question is what to do after you have found the pattern?
 
Physics news on Phys.org
fvnn said:
My question is what to do after you have found the pattern?
Whatever the problem tells you. You could write the general form of the pattern (after applying the definition of $T$ $n$ times). You could write the explicit formula for $T$ when $n$ is a power of 2 for a given $T(1)$ and then prove it by induction.
 
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top