Tagged Questions
1
vote
3answers
73 views
Using induction to verify a statement
I have to prove that this statement is true.
For $n = 1, 2, 3, ...,$ we have $ 1² + 2² + 3² + ... + n² = n(n + 1)(2n + 1)/6$
Basically I thought I'd use induction to prove this. Setting $n = p+1$, I ...
6
votes
5answers
82 views
Prove that $3^n>n^4$ if $n\geq8$
Proving that $3^n>n^4$ if $n\geq8$
I tried mathematical induction start from $n=8$ as the base case, but I'm stuck when I have to use the fact that the statement is true for $n=k$ to prove ...
0
votes
2answers
58 views
How to prove this inequality by using induction?
If $x,y$ are distinct real numbers such that $x+y>0$ and $n\ge 1$, then $2^{n-1}(x^n+y^n)\ge (x+y)^n$.
It is obvious for $n=1$. How to do the rest by using induction?
1
vote
1answer
46 views
Combinatorics identity sum of
Prove that:
$$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$
By using only combinatorics identities.
2
votes
1answer
146 views
Another hat problem
A finite number of prisoners, after being given their hats (black or white), are able to see one another but themselves, and then they are ordered to jot down their guess on the color of their own ...
0
votes
2answers
50 views
Prove summation using induction [duplicate]
$$\sum\limits_{i=1}^n i^3 = \left(\frac{n(n + 1)}{2}\right)^2$$
My basis step is $P(1)$ sets the $LHS = RHS = 1$.
For the inductive step, I assume $n = k$ holds for $k+1$. On the $RHS$:
...
4
votes
4answers
113 views
If $S_n = 1+ 2 +3 + \cdots + n$, then prove that the last digit of $S_n$ is not 2,4 7,9.
If $S_n = 1 + 2 + 3 + \cdots + n,$ then prove that the last digit of $S_n$ cannot be 2, 4, 7, or 9 for any whole number n.
What I have done:
*I have determined that it is supposed to be done with ...
4
votes
1answer
54 views
Proving Inequality using Induction $a^n-b^n \leq na^{n-1}(a-b)$
I was trying to prove this inequality using induction, but couldn't do.
Question: Suppose $a$ and $b$ are real numbers with $0 < b < a$. Prove that if $n$ is a positive integer, then:
...
1
vote
1answer
47 views
How to prove that $n^k = O(2^n)$
I'm having issues trying to prove this.
The Big Oh definition is: f(n) = O(g(n)) if exists a real constant $c > 0$ and $n_0 \in \Bbb N $ in such a way that for all $n \ge n_0$ we have f(n) $\le$ ...
1
vote
2answers
59 views
Induction proof [ little-o notation ]
I have to prove that $ 2^n = o(n!) $, that is, $ \forall c \gt 0 \quad \exists$ $ n_0 \in \mathbb N$ such that $ \forall n \ge n_0$ we have $ 2^n \lt c.n! $
Well, this is what I did so far:
First I ...
0
votes
1answer
54 views
Prove by induction $ \sum^n_{i=1}(i-1/2) = n^2/2 $
This is a question from a test that I wrote and I'm wondering how do you solve it.
Prove by induction that
$$ \sum^n_{i=1}(i-1/2) = \frac{n^2}{2} $$
*Provide a Base Case, Inductive Hypothesis, and ...
0
votes
1answer
86 views
Solving Recurrence Relation with Forward Substitution
I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with
$$
T(n) = 4T(n/3)
$$
For all $n > 1$ ...
0
votes
2answers
48 views
Formal definition of Mathematical Induction & Strong Induction
I have been reading some notes on Induction and Strong Induction and fully understand how they work. However I was interested in a formal/mathematical way of expressing their definition and was ...
1
vote
1answer
36 views
using mathematical induction to prove two recursive function
I have two function which are
$$\begin{align*}
&T_1(n)=2T_1\left(\frac{n}2\right)+n\\\\
&T_2(n)=\begin{cases}
\frac{n(n-1)}2,&\text{if }n<8\\\\
...
0
votes
2answers
51 views
Stuck on a proof divisibility by induction
Show using induction that $n^3-n$ is divisible by 6 $\forall n\ge1, \quad n \in \mathbb{N}$
First off i show that the basis step: $1^3-1=0, \quad \frac{0}{6}=0$
Now I factorised it and set it ...
0
votes
3answers
108 views
Proof by induction for a recursive function $F(n) = F(n–1)+F(n–2)$
I'm having a lot of trouble with the following homework question:
Consider the following recursive function:
Base Case: $F(0) = 0,F(1) = 1$.
Recursive Step: $F(n)=F(n−1)+F(n−2)$ for all ...
-2
votes
2answers
58 views
Show: $\prod_{i=2}^n \left(1-\frac{1}{i^2}\right) = \frac{n+1}{2n}$
Show: $$\prod_{i=2}^n \left(1-\frac{1}{i^2}\right) = \frac{n+1}{2n}$$
for $n\geq 2$.
2
votes
2answers
108 views
Find the demonstration error for the statement “All positive integers are equal”
All positive integers are equal, that is, for each $n \in \mathbb{N}$ the assertion $P(N): 1 = \cdots = n$ is true.
(i) $P(1)$ is true because $1 = 1$
(ii) Suppose that $P(n)$ is true, then $1 = ...
1
vote
6answers
60 views
Need help with a proof by induction
Prove by induction that $(n+1)+(n+2)\cdots+2n=\frac{1}{2}n(3n+1)$
I was not really sure how to do this, but I assumed that the case holds for $n=k$, therefore ...
2
votes
2answers
103 views
$ a $ and $b$ are real numbers with $0 < b < a$. Prove that if $n$ is a positive integer, then $a^n - b^n \leq na^{n-1}(a - b)$.
I'm taking a basic discrete math course and I'm having a hard time with Mathematical Induction.
The problem is stated as:
Suppose that $ a $ and $b$ are real numbers with $0 < b < a$. Prove ...
0
votes
1answer
59 views
Show by induction -Analysis
Show by induction that for all $z\notin\{-1,1\}$ one has
$$\sum_{k = 0}^n z^{2 k} = \frac{1-z^{2n+2}}{1-z^2}\ .$$
Deduce that if $z<1$,
$$\sum_{k = 0}^\infty z^{2 k} = \frac{1}{1 - z^2}\ .$$
1
vote
3answers
67 views
Proving $(5-\frac5k )(1+\frac{1}{(k+1)^2}) \le 5 - \frac{5}{k+1}$
Can anyone tell me what I am doing wrong? need to prove for $k\ge2$
$$(5-\frac5k )(1+\frac{1}{(k+1)^2}) \le 5 - \frac{5}{k+1}$$$$(5-\frac5k )(1+\frac{1}{(k+1)^2})= 5(1-\frac1k)(1+\frac1{(k+1)^2})$$
...
0
votes
2answers
58 views
Proving by induction $P_n \le 5 - \frac5n$
for $n\ge1$ let:$$P_n = (\frac21).(\frac54).(\frac{10}9).(\frac{17}{16})...(\frac{n^2+1}{n^2}) = \prod^n_{k=1}(\frac{k^2+1}{k^2}). $$
Prove by induction for $n\ge 2$: $$P_n \le 5 -\frac5n $$
I did ...
5
votes
1answer
61 views
Proving the following inequality using induction?
I need to prove by induction that $Q_n \ge\frac{10}{3}-\frac5{3n}$ for $n\ge2$$$
Q_n = ...
0
votes
3answers
53 views
Proving the formula is correct by induction
$$P_n = \prod^n_{k=2} \left(\frac{k^2 - 1}{k^2}\right)$$ Someone already helped me see that $$P_n = \frac{1}{2}.\frac{n + 1}{n} $$ Now I have to prove, by induction, that the formula for $P_n$ is ...
3
votes
1answer
32 views
Formula for this sequence?
$P_n= \prod^n_k_=_2 \frac{k^2-1}{k^2}$ for $n \ge 2$
I calculated $P_1 to P_3$ . I have been trying to come up with a formula but I can't really see any pattern.
$P_2 = \frac{3}{4} , P_3 = ...
4
votes
4answers
124 views
Prove by Mathematical Induction: $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$
Prove by Mathematical Induction . . .
$1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$
I tried solving it, but I got stuck near the end . . .
a. Basis Step:
$(1)(1!) = (1+1)!-1$
$1 = ...
2
votes
2answers
148 views
Induction Proof: $\sum_{i=1}^{n+1} i \cdot 2^i = n \cdot 2^{n+2}+2 $
Prove by Mathematical Induction . . .
$$\sum_{i=1}^{n+1} i \cdot 2^i = n \cdot 2^{n+2}+2 $$
for all $n \geq 0$
I tried solving it, but I got stuck near the end . . .
a. Basis Step:
$1\cdot 2^1 ...
2
votes
3answers
117 views
Something kind of like proving the euclidean Algorithm by induction
Let a > b be positive integers. In applying the Euclidean algorithm,
we have $a = b q_0$ + $r_0$, $b = r_0 q_1 + r_1$, and $r_{n-1} = r_n q_{n+1} + r_{n+1}$, for all $n > 0$. Prove by induction ...
3
votes
2answers
117 views
Prove by Induction
For $n\in \mathbb{N}$ and $z\in \mathbb{C}$:
$\sin{(nz)}=\sum _{ k=0 }^{ n }{ \binom{n}{k} }\frac{1}{2i}(i^k-(-i)^k)(\cos{z})^{n-k}(\sin{z})^k $
$\cos{(nz)}=\sum _{ k=0 }^{ n }{ ...
2
votes
2answers
90 views
$9^n \equiv 1 \mod 8$
I would like someone to check this inductive proof (sketch)
The base case is clear. For the inductive step, it follows that $8 \mid 9^{n+1} - 9 = 9(9^n - 1)$ by the indutive hyp. So $9^{n+1} \equiv ...
0
votes
3answers
40 views
Prove $\sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}$ by induction
I was assigned two induction problems that I tried to solve. One was easy to solve using the following method, but one got me stuck. Problem:
Prove by induction on $n \geq 1$ that for every $a ...
1
vote
1answer
52 views
Example where $P(n)$ is not valid for induction?
I am studing for my math exam on friday and at the moment I am doing a examples about induction:
However, I am struggeling at this question:
Give an example where $P(n)$ is not valid even if the ...
5
votes
4answers
576 views
Prove that given a nonnegative integer $n$, there is a unique nonnegative integer $m$ such that $(m-1)^2 ≤ n < m^2$
Prove that given a nonnegative integer $n$, there is a unique nonnegative integer $m$ such that $(m-1)^2 ≤ n < m^2$
My first guess is to use an induction proof, so I started with n = k = 0:
...
0
votes
2answers
118 views
3 Homework Question. Counting, Induction and Pigeonhole principle
First hello all.
i have a homework with 10 question but im stuck with 3 i searched about them everywhere read other colleges lectures but i couldnt solved them finally i desired to ask here
...
1
vote
3answers
71 views
Induction prove, how to come to $n\cdot(n+1)$
I am trying to solve an induction problem. Here are the steps for the example.
Prove this equation $$
1\cdot2 + 2\cdot3 + 3\cdot 4 + 4\cdot 5+\dots + \cdots +(n-1)\cdot n ...
0
votes
1answer
99 views
Proof by induction for Stirling Numbers
I am asked this:
For any real number x and positive integer k, define the notation
[x,k] by the recursion [x,k+1] = (x-k) [x,k] and [x,1] = x.
If n is any positive integer, one can now ...
0
votes
7answers
129 views
Proving divisibility by strong induction
I'm trying to prove by induction the following statement without success:
$$\forall n \ge 2, \;\forall d \ge 2 : d \mid n(n+1)(n+2)...(n+d-1) $$
For the base case: $n = 2$, $d = 2$
$2\mid 2(2+1)$ ...
1
vote
1answer
68 views
Two questions with mathematical induction
First hello all, we have a lecture. It has 10 questions but I'm stuck with these two about 3 hours and I can't solve them.
Any help would be appreciated.
Question 1
Given that $T(1)=1$, and ...
1
vote
1answer
87 views
Sequences with induction and proving. Polynomial and rational functions
$1.$We define a sequence of rational number {$a_n$} by putting $$a_1 =3,\;\text{ and}\;\; a_{n+1} = 4 - \frac{2}{a_n} \text{ for all}\; n \in \mathbb{R}.\;\text{ Put}\;\; \alpha = 2 + \sqrt{2}.$$
...
0
votes
2answers
79 views
Induction proof of boundedness of a sequence [duplicate]
Possible Duplicate:
We define a sequence of rational numbers {$a_n$} by putting $a_1=3$ and $a_{n+1}=4-\frac{2}{a_n}$ for all natural numbers. Put $\alpha = 2 + \sqrt{2}$
Could someone help ...
0
votes
2answers
193 views
Recurrence relation, induction and Fibonacci numbers
1.(a) Consider the recurrence relation $a_{n+2}a_n = a^2_{n+1} + 2$ with $a_1 = a_2 = 1$.
(i) Assume that all $a_n$ are integers. Prove that they are all odd and the integers $a_n$ and $a_{n+1}$ are ...
1
vote
2answers
62 views
mathematical induction with functions
a function $f$ satisfies the following conditions:
$$\begin{align*}
&f(1)=1\\
&f(n)=f(n-1)+2\sqrt{f(n-1)}+1\quad\text{for integers}\quad n\ge 2
\end{align*}$$
Find a formula that might be ...
3
votes
2answers
33 views
Reason behind particular induction step
I'm wondering why and how you get some of these steps in an Induction proof.
Okay, so the question is to prove the following statement by induction:
$1 - x + x^2 - x^3$ $+ ... +$ $x^{2n-2} = ...
1
vote
3answers
137 views
Prove that $\bigcap\limits_{i = 1}^n {\left( {{A_i} - B} \right)} = \bigcap\limits_{i = 1}^n {{A_i}} - B$
Prove that if $A_1, A_2, \ldots , A_n$ and $B$ are sets, then
$$(A_1 − B) \cap (A_2 − B) \cap \cdots \cap (A_n − B) = (A_1 \cap A_2 \cap \cdots \cap A_n) − B.$$
0
votes
0answers
200 views
Proving a recurrence relation by induction
Hi I have the following recurrence relation:
$$T(n) = \begin{cases}
1, & \text{if $n=2$} \\
2T\left({n \over 2}\right) + 4, & \text{if $n > 2$} \\
\end{cases}$$
Where $n$ can be ...
2
votes
2answers
111 views
how: mathematical induction prove inequation
Provided that $p\geq-1$, prove $(1+p)^n\geq1+np$ for all integers $n\geq 0$
Also, where in the calculation do I use $p\geq -1$?
Thanks guy!
2
votes
2answers
158 views
Prove by induction $\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}$ for $n\ge1$
Prove the following statement $S(n)$ for $n\ge1$:
$$\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}$$
To prove the basis, I substitute $1$ for $n$ in $S(n)$:
$$\sum_{i=1}^11^3=1=\frac{1^2(2)^2}{4}$$
Great. ...
0
votes
1answer
92 views
Homework proof Extended Transition Function by mathematical induction
Let M = (Q,∑, q0,A, δ) be an FA. Below are other conceivable methods
of defining the extended transition function δ∗. In
each case, determine whether it is in fact a valid definition of a function
on ...
1
vote
1answer
199 views
Proof by induction: $n^{n+1} > (n + 1)^n$, $(1 + x)^n \ge 1 + nx$, other inequalities
I'm struggling around my homework. I hope someone will point me the right direction for solving following examples:
Prove that $n^{n+1} > (n + 1)^n$ for $n > 2$;
Prove that $(1 + x)^n \ge 1 + ...
