0
votes
0answers
20 views

Prove that (√ 2)^(log(n)) + log^2(n) + n^10 = O(2^n) [duplicate]

This example question has me rather stumped. I'm not sure where to even start with the log(n) terms. The only clue it gives is "There is at least one non-trivial induction to do as part of the ...
1
vote
1answer
20 views

Is there a proof for what I describe as the “recursive process of mathematical induction for testing divisibility”.

I was working on my homework for Discrete Math, and we were asked to "Prove: $6 | n^{3}+5n$,where $n\in \mathbb{N}$" my solution varied significantly from how I have seen it done by others. I noticed ...
0
votes
1answer
17 views

Proving order of magnitude

Generally how much proof must be given to prove a statement of order-of-magnitude? for example: $n^2 + 2 log (n) = O(n^2)$ $2 log (n)$ has a lower order of magnitude than $n^2$ so it can be argued ...
2
votes
2answers
78 views

Proofs with Induction Imply Proofs Without Induction?

Assume we can prove $\forall x P(x)$ in first order Peano Arithmetic (PA) using induction and modus ponens. Does this mean we can prove $\forall x P(x)$ from the other axioms of PA without using ...
0
votes
2answers
186 views

is it possible to prove the method of mathematical induction itself?

Since the method of mathematical induction follows some sort of 'algorithm', would the method itself be provable? namely, give that the method of mathematical induction is as follows: if S is a ...
3
votes
3answers
376 views

Statements true for all integers but not provable by induction

Is there any examples of statements P(n) such that "for all $n>1$, P(n)" is provable, but P(n)=>P(n+1) is not provable? (without using some mild deformation of "for all $n>1$, ...
4
votes
1answer
183 views

How does adding the full second order induction scheme affect the consistency strength of subsystems of second order arithmetic?

Following on from my question about $\omega$-models, I'm interested in the interaction between subsystems of second order arithmetic with restricted induction such as $\mathsf{RCA}_0$ and those which ...