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 ...

learn more… | top users | synonyms

0
votes
1answer
12 views

Let n be an arbitrary natural number and let the property P(n) be the equation 2 · 6 · 10 · 14 · … · (4n - 2) = (2n)! / n!

Here's my proof: Base Case: Show that P(1) is true: n = 1 (4(1) - 2) = (2(1))! / (1)! 4 - 2 = 2! / 1 2 = 2 The base case holds. Induction Step: Show that for all natural numbers k, if P(k) is ...
0
votes
1answer
31 views

Determining if two statements are equivalent, logical sense.

I am confused, I am working with proofs and I have the following statement to work with $\forall n\in\mathbb{N},P(n) \implies P(n+1)$ I have a second statement $\forall n\in\mathbb{N}, ...
1
vote
1answer
43 views

Integration by parts, proving inductive case

${1\over2}\int_{-\pi/2}^{\pi/2}cos^{2n-1}(x) dx$ Inductive step: Show that the $integral={(2n-2)(2n-4)...\over (2n-1)(2n-3)...}$ for $n\ge2$ $T(n+1)$=... Attempted int. by parts using ...
1
vote
1answer
29 views

Prove using structural induction?

First off: I am not sure if I have posted to the correct site, but I am quite lost with this question. I am in a theory of computation class after taking 1.5 years off school and we are on ...
1
vote
1answer
28 views

Induction proof of the area of a square

English is not my first language, so I'm sorry if I'm not very clear. I can clarify any question you have. Also, I don't know how to use that math formatting so I apologize for it. So I was asked to ...
0
votes
3answers
27 views

Solving a question by mathematical induction [duplicate]

Question : Prove that $$ \sum_{k=1}^n\frac{1}{\sqrt{k}}\le 2\sqrt{n}-1 $$ for all positive integers $n$. I've been thinking a solution for this question for hours but still can't solve it.
0
votes
1answer
14 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 ...
0
votes
7answers
77 views

Prove by induction that $n(n+1)(n+5)$ is multiple of 3

$$n(n+1)(n+5) = 3d$$ I cannot figure out how to solve this homework question. A friend gave me a solution I couldn't make sense of, and I hope there's something easier out there. Also, what would be ...
1
vote
2answers
37 views

Proving by induction, if the base case fails to meet the main condition, what do we do?

I have to determine the number $x$ of subsets with odd cardinalities of a set $S$ and then prove that I'm correct. I determined the number $x$ is obtained using the formula $2^{n-1}$ where $|S| = n$. ...
0
votes
2answers
53 views

Using induction to prove a formula for $\sin x+\sin 3x+\dots+\sin (2n-1)x$

I'm working from the text "Intro To Real Analysis" by William Trench. Here is what I have thus far. I will prove using Mathematical Induction that $\sin x+\sin 3x+...+\sin (2n-1)x=\frac{1-\cos ...
1
vote
4answers
61 views

Proving $4^n > n^4$ holds for $n\geq 5$ via induction.

I know that it holds for $n=5$, so the first step is done. For the second step, my IH is: $4^n > n^4$, and I must show that $4^{n+1} > (n+1)^4$. I did as follows: $4^{n+1} = 4*4^n > 4n^4$, ...
0
votes
0answers
16 views

Sum of convolution of divisor function [duplicate]

For every integer $k$ let $d_k: \mathbb{N} \rightarrow \mathbb{C}$ be defined recursively as $d_0 = \mathbf{1}$, $d_k = d_{k-1} * \mathbf{1}$. So for example $d_1 (n) = d (n) = \sum_{d \vert n} 1$ is ...
2
votes
1answer
34 views

Recursive definition of multiplication

I have the following function: $$ \begin{cases} mul (a, 0) = 0&\mbox{if }n=0\\ mul (a, n) = mul (2a, \frac{n}{2})&\mbox{if }n\mbox{ is even}\\ mul (a, n) = mul (2a, \frac{n-1}{2}) + ...
0
votes
0answers
26 views

Proof using induction on sequences

Here's a theorem I'd like to prove using weak induction: Theorem 1: The sequence $\{x_n\}$ is recursively defined as follows: $$x_n=\cos(x_{n-1}) \sin(x_{n-2}) \text{ for } n \geq 2$$ where $x_0 = ...
1
vote
2answers
44 views

Lucas Numbers Proof $L_n = \alpha^n + \beta^n$

Proof by Induction: Lucas numbers are recursively defined as: $L_n = L_{n-1} + L_{n-2}$ where $L_1 = 1$ and $ L_2 = 3 $for $n \ge 3$ Show that: $L_n = \alpha^n + \beta^n$ for $\alpha = ...
0
votes
1answer
25 views

conjecture formula/prove by induction

Conjecture formula from following equations, and prove conjecture: $1=1,\\2+3+4=1+8,\\5+6+7+8+9=8+27,\\10+11+12+13+14+15+16=27+64\\$ $S(n)=\sum_{i=(n-1)^2+1}^{n^2}i=(n-1)^3+n^3$ ...
0
votes
1answer
32 views

Mathematical Induction

The sequence of real numbers $a_1$, $a_2$, $a_3$...is such that $a_1$ $=$ $1$ and $a_{n+1} = (a_n + \frac{1}{a_n} )^{\lambda}$ ,where $\lambda$ is a constant greater than 1. Prove by mathematical ...
0
votes
0answers
66 views

Fibonacci sequence: Prove the formula $f_{2n+1}=f_{n+1}^2 + f_n^2$ [duplicate]

I can't seem to figure out this proof. I'm using weak induction and always get stuck during the inductive step. Prove for n > 0: $$f_{2n+1} = f_{n+1}^2 + f_n^2$$
4
votes
5answers
307 views

Proof by induction involving inequalities

Problem: If $n$ is a natural number and $n\geq4$, then $3^n \geq 2n^2 + 3n$. (Prove by Induction.) Attempt at solution: 1) Given: $n$ is a natural number, $n \geq 4$. 2) Let $P(n)$ be the statement ...
1
vote
1answer
32 views

Series Induction problem set:

For all $n$ belonging to $\mathbb N$, let $A_n$ be the number of subsets of $\{1,2,\ldots,n\}$ that do not contain any two consecutive members (including $\emptyset$); (a) Show that $A_n$ is the ...
0
votes
2answers
67 views

prove by induction, not for natural numbers this time, but for real numbers

Prove by induction: suppose there's a vertical column, infinitely tall from the ground. from 0 inches to 2 inches are dangerous zone, and up from 2 inches are safe zone. If you care climbing this ...
3
votes
0answers
26 views

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,...,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! ...
0
votes
3answers
50 views

If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem: If $a, b, c \in ...
2
votes
1answer
40 views

If $a_n=n^\frac 1n-1, n \in \mathbb N$ prove that $0 \le a_n \le \sqrt {2/n}$?

If $a_n=n^{\frac{1}{n}}-1$, $n\in\mathbb{N}$, prove that $0\le a_n\le\sqrt{\frac{2}{n}}$. I tried with induction and signs, got nowhere. Any help is appreciated.
-2
votes
1answer
29 views

Probability and Induction help [on hold]

Let $Y=X_1+X_2+ \cdots+X_n$ where $X_1, X_2, \ldots, X_n$ are independent Bernoulli random variables, each with probability of success equal to $q$. Use induction to prove that $Y$ has a Binomial ...
1
vote
4answers
40 views

Prove that the power set of S contains $|2^n|$ elements

From the above explanation, I don't understand why the set that contains {a} will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$ The construction of a new set $S$ is the union of ...
0
votes
1answer
33 views

Proof By Induction that $3^{(2^n)} -1$ is divisible by $2^{(n+2)}$ [on hold]

How do I prove the $(n+1)$-th case for this equation?
1
vote
3answers
37 views

Prove a sum formula by induction

I am to prove through induction that $$\sum_{k=1}^n (2k-1)^2 = \frac{n(2n-1)(2n+1)}{3}$$ And well, my method seems to be working, but I get stuck when I'm nearly done. First I prove the formula work ...
0
votes
1answer
29 views

Formula for the floor of $n/2$, to be proved by induction

How do you compute this when the base case is all wrong?
2
votes
3answers
45 views

Prove or Disprove n! = BigOh(2^n) via mathematical induction.

My computer science professor has us tasked with proving or disproving the statement the n! = BigOh(2^n). We are then suppose to say if it's always true, always false, or non-conclusive, ...
0
votes
1answer
19 views

Can someone help me complete this easy proof by induction

$P(n): for -1<x => (1+x)^n >= (1+nx)$ $P(1): (1+x) >= (1+x)$ $P(n+1): (1+x)^{(n+1)} = (1+x)^n*(1+x) ....$ where to go from here?
3
votes
2answers
145 views

Can someone please explain the axiom of induction in lay term?

Axiom of Induction To me, it says, for all P such that P(0) AND for all k is an element of natural numbers P(k) implies P(K+1) implies for all n is am element in the natural numbers of P(n) But ...
-1
votes
1answer
26 views

Induction Proof of Inequality Involving Summation [closed]

I really need help with the following exercise! Show with induction that $\sum _{k=1}^n\left(k^2\right)<n^3$, for $n>1$ .
5
votes
1answer
63 views

Nested Radicals Induction

How can I show that $\sqrt[2]{2+\sqrt[3]{3+\sqrt[4]{4+\cdots}}} $ (repeated $n$ times) is irrational using induction? I know the base case for $n=1$ looks like: $\sqrt[2]{2}$ is irrational. I also ...
0
votes
2answers
60 views

Sum of the first $n$ numbers that is neither divisible by 2 nor 3.

Show that the sum of the first $n$ positive integers that are divisible by neither 2 nor 3 is $\frac{3}{2}n^2-\frac{1}{2}$ if $n$ is odd and is $\frac{3}{2}n^2$ if $n$ is even. I have verified that ...
1
vote
4answers
54 views

Prove this by induction?

I'm trying to do homework problems and for the most part I've been getting the results. For this one though, I am having some trouble since its $2^n$ and I can't relate it properly: So obviously, the ...
1
vote
2answers
28 views

Induction for recurrence

I'm trying to understand an induction proof that aims to prove some function is in $O(n\log{ n})$. It's on page 5 of this PDF: https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf ...
3
votes
5answers
402 views

proof by induction - explanation on it

Proof by induction. It's pretty useful, and the purpose of it makes a lot of sense. However one thing has always bothered me concerning it. So when you apply induction, one has a base case where you ...
0
votes
0answers
58 views

Induction — n to n+1 [duplicate]

I'm trying to understand an induction proof that aims to prove some function is in $O(n\log{ n})$. It's on page 5 of this PDF: https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf ...
0
votes
2answers
40 views

prove that the sum to n terms of the sequence is $n(n+1)/2(2n+1)$ [duplicate]

Prove that the sum to n terms of the Sequence: $1^2/(1×3),2^2/(3×5),3^2/(5×7),...$ is $ n(n+1)/2(2n+1).$ Im having trouble with this question, firstly ive begun by stating that p(n) denotes the ...
0
votes
1answer
31 views

Induction Proof: Round Robin

In a round-robin tournament, each team plays every other team exactly once. Show that if no games end in ties, then no matter what the outcomes of the games, there will be some way to number the teams ...
1
vote
1answer
45 views

Strong mathematical induction with a sequence

The question: The terms of a sequence are given recursively as $a_0 = 1$, $a_1 = 1$ and $a_n=2a_{n-1} + 3a_{n-2}$ for $n \geq 2$ prove by mathematical induction $a_n = \frac12(3^n) +\frac12(-1)^n$ ...
0
votes
0answers
11 views

about concrete mathematics 5.8 last proof.

concrete mathematics 2th 5.8 proof Gosper-Zeilberger algorithm is guaranteed to succeed in an enormous number of cases.... p241:...
0
votes
3answers
30 views

Induction assuming n-1

In induction, I always thought that one assumed that some statement was true for n and then showed it's true for $n+1$. But in one proof I am trying to understand, I think that they assume that it's ...
0
votes
0answers
11 views

Recursion, Induction, and Vinogradov Notation

I have a recursion relation $$ S(x, p_{n+1}, k) = S(x, p_n, k) - c(p_n) S\bigg(\frac{x}{p_n}, p_n, k p_n\bigg) + S\bigg(\frac{x}{p_n^2}, p_n, k p_n^2\bigg) \quad $$ where $c(l)$ are constants such ...
1
vote
2answers
45 views

Structural Induction help

Give a recursive definition of the set of bit strings that contain twice as many 0s as 1s. please any guidance would be appreciated this is a hw problem.
0
votes
0answers
16 views

Recursively defined sequences and Explicitly defined sequences

Let $x_n$ be a real number sequence. I believe boundedness for $x_n $ is defined as : $x_n$ is bounded above iff $\exists c \in R, \forall n \in N , x_n \leq c $ . $x_n$ is bounded ...
0
votes
0answers
22 views

What is the intuition behind the solution to the “Surveyevor” problem?

I was looking at the "Surveyevor" problem in the MIT OCW site: here. This is more or less what it says: In a new reality TV series called Surveyevor, a group of contestants is placed on a small ...
2
votes
2answers
57 views

Prove by induction: $1(1!)+\cdots + n\cdot n!$ = (n+1)! - 1

Induction step. $1(1!) + ... + n(n!) = (n+1)! - 1$ $1(1!) + ... + n(n!) + (n+1)(n+1)! = (n+1)! - 1 + (n+1)(n+1)!$ So, I don't understand how to get $(n+2)! - 1$ from $(n+1)! - 1 + (n+1)(n+1)!$. ...
3
votes
3answers
64 views

In proof by induction, what happens if P(n) is false for a specific case or the base cases are false? Can we still deduce meaningful conclusions?

The principle of mathematical induction works basically because of the following: If we have a predicate $P(n)$, then if we have: P(0) is true, and P(n) $\implies$ P(n+1) for all nonnegative ...