Tagged Questions

Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

111 views

What actually constitutes a *definition* for a function?

I'm reading Enderton's text on logic trying to justify ( to myself ) the use of induction on recursively defined sets. This is of course used repeatedly in trying to prove results about well-formed ...
19 views

How do you solve a recurrence with a functin through induction?

I found the answer in part-A by substitution, as O(n) from; T(n/2^k) = T(1).... n/2^k = 1..... so k = 1og2(n)..... T(log2(n)) = T(n/n)+5.... so O(n) IS THE ANSWER, Correct me if am wrong because am ...
119 views

Showing the $n$-th derivative of $\cos x$ by induction

I was asked to show that the $n$-th derivative of $\cos x$ is $\cos(\frac{n\pi}{2} + x)$. My progress : By induction, I proved it was true for $n=1$. Then I assumed it was true for $n = k$ so now I ...
104 views

42 views

Use the recursive definition, $f(k) + k² + 2k -3$, to prove that, for any $n ∈ \Bbb N,\ f(n) = n² - 4$.

Here's what I have so far: Let $f: \mathbb{N} - \{1\} \to \mathbb{N}$, such that $f(x) = (x+2)(x-2)$. Formulate a recursive definition for $f$ including both the base case $f(2) = 0$ and a ...
105 views

coin problem with two coins, inductive proof

Adjustment This proof is flawed. I want to ask something about the coin problem with two coins. Let $a,b$ be to numbers in $\mathbb{N} \setminus \{0\}$ (elsewhere I include zero) which have no prime ...
70 views

Finding a formula for $1+\sum_{j=1}^n(j!)\cdot j$ using induction

I need help with finding the formula and proving it by induction. Am stuck, but the professor says we should know this by now.
40 views

Direct proof of principle of transfinite induction

This is a problem from the book Set theory by You-Feng Lin. Principle of Transfinite Induction Let $(A,\le)$ be a well-ordered set. For each $x \in A$, let $p(x)$ be a statement about $x$. If for ...
63 views

Prove $1! + 2! + . . . + n! < (n + 1)!$ using mathematical induction [duplicate]

$1! + 2! + . . . + n! < (n + 1)!$ This question has left me stumped for quite some time. I am not sure how to approach it. (I am really bad at induction).
48 views

how to prove $1/n (1-(1/2)^n)$ decreasing without using differentiation

$a(n)=1/n (1-(1/2)^n)$ prove $a(n+1)<a(n)$ for n>0 by differentiating slope comes negative and then we can prove it . but i wanted to solve it without that . can someone help
I've got this recursive equation: $$T(n) = \begin{cases} 2, & \text{if n = 2} \\ 2T(n/2) + n, & \text{if n = 2^k where k > 1, k \in \mathbb{N} } \\ \end{cases}$$ I know I should ...