0
votes
1answer
27 views

Inductive proof on r

Let $r, n ∈ N$ and let $r ≤ n$. Give an inductive proof for: $$ {n+1 \choose r + 1} = ∑_{k=r}^n {k \choose r} $$ Step 1: We will prove this using induction on n. n = 1 Step 2: n = k, prove for n = ...
0
votes
1answer
19 views

Proof by induction with two variables

Giving proof by induction is normally very straight forward: $n+1$ and such. But how do you deal with two variables $m$ and $n$? Given this problem, how do I ensure that I'm proving for $n+1$ and ...
0
votes
1answer
33 views

Induction proof divisible by 5

Prove that for all n ∈ N, prove that $ 3^{3n+1} + 2^{n+1} $ is divisible by 5. So far what I've gotten is: Step 1: We will prove this by using induction on n. Assume the claim is true when n = k. ...
2
votes
1answer
28 views

Gossip problem proof by induction

Question Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they ...
1
vote
3answers
52 views

Hard Mathematical Induction [duplicate]

I have a mathematical induction question and I know what I need to do just not how to do it. The question is: Prove the equality of: $$(1 + 2 + . . . + n)^2 = 1^3 + 2^3 . . . + n^3$$ Base ...
0
votes
2answers
61 views

How do i prove these type of questions? I am Really stuck.

How do I solve this textbook question: If we let $n\geq 1$ be an integer and define $A_n$ to be the number of bitstrings of length $n$ that do not contain $101$ How do I determine $A_1$, $A_2$, ...
1
vote
1answer
46 views

How can I solve this recursion question, I am really stuck. [duplicate]

I am doing a couple of exercise questions, How do I show that if we let $n \geq 1$ be an integer, and if we consider $n$ people $P_1$,$P_2$,...,$P_n$. If we let $A_n$ be the number of ways these $n$ ...
0
votes
1answer
38 views

prove conjunction of consecutive implications

$n\ge 2,p_1,p_2,p_3,...,p_n,p_{n+1}$ are statements. Prove $(p_1\rightarrow p_2)\wedge (p_2\rightarrow p_3)\wedge ...\wedge (p_n\rightarrow p_{n+1})$ $\Rightarrow (p_1\wedge p_2\wedge ...
2
votes
5answers
84 views

Prove that $\left(\sum_{k=1}^{n}k\right)^2=\sum_{k=1}^{n}k^3$ holds true for $n ≥ 1$

I've been trying to figure out this proof for way too long now, I'm just not sure where to begin for the inductive step. Any guidance would be greatly appreciated.
0
votes
4answers
44 views

Method of Proof (Computer Science) [duplicate]

Prove that $1+r+r^{2}+...+r^{n-1}=\frac{r^{n}-1}{r-1}$, $r$ a positive integer, $r \neq 1$
1
vote
1answer
58 views

Mathematical induction base case is not initial

Prove by induction that $$1+2+3+\cdots+n= \frac{n(n+1)}{2}$$ for all integers greater than or equal to $2$ How can you solve this if the base case is not $1$? I thought it might be a strong ...
1
vote
2answers
45 views

Help with induction proof for recurrent function

I am having issues with the following inductive proof. Prove by induction on $n$ that $$ a(n) = n!\bigg(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(n-1)!}\bigg)$$ for all $n \geq 1,$ where ...
-1
votes
2answers
53 views

Mathematical induction used on Fibonacci Sequence

I have no clue how to go about doing this question using induction. It states that the Fibonacci sequence is defined as: F0 = 0 F1 = 1 Fn = Fn-2 + Fn-1 for n>=2 Let S(n) = Fo + F1 + F2 +...+ ...
0
votes
0answers
33 views

Do I have to prove it by induction with respect to $n$ or to $k$?

I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n-1)$. We have to suppose that $n=2^k, k \geq ...
0
votes
1answer
36 views

Finding $a_n$ if $a_0=a_1=1,a_{n+1}=n(a_n+a_{n-1})\ \ (n\ge 1).$

The problem states: Suppose $a_0,a_1,a_2,...$ is a sequence such that $$a_0=a_1=1,\ \ \ a_{n+1}=n(a_n+a_{n-1})\ \ \ (n\ge 1).$$ Guess a formula for $a_n$, valid for $n\ge 1$, and use mathematical ...
2
votes
1answer
62 views

Do we have to claim it? If so, at which point?

I have to solve the recurrence relation $$T(n)=\left\{\begin{matrix} 3T\left (\frac{n}{4} \right)+n & , n>1\\ 1 &, n=1 \end{matrix}\right.$$ and prove by induction that the solution I ...
2
votes
0answers
42 views

Number or regions formed when $n$ points on a circle are joined

The maximum number $R_{n}$ of regions formed when $n$ points on a circle are joined in pairs is $\frac{1}{24}\left(n^{4}-6n^{3}+23n^{2}-18n+24\right)$. This is a fact that I have read in several ...
4
votes
4answers
218 views

Mathematical Induction Question, Proof Help [duplicate]

Prove using Mathematical Induction that for all natural numbers ($n>0$): $$ \frac 1 {\sqrt{1}} + \frac 1 {\sqrt{2}} + \cdots + \frac 1 {\sqrt{n}} \ge \sqrt{n}. $$ ...
0
votes
3answers
44 views

Prove by induction for every integer$\; n\ge 5$, $2^n\gt n^2$.

Prove by induction for every integer$ \;n\ge 5$, $2^n\gt n^2$. My try: $$p(n):\;2^n>n^2$$ verify $P(5)$ $$ p(5):\;2^5>5^2 = 32 > 25 $$ Of course the trick is in the induction step and ...
1
vote
1answer
13 views

Sequence problem by Strong induction

Problem is as follows: Let $X_0 = 3$ and let $X_{n+1} = X_n + \cdots + x_1 + x_0 + 3$ for $n ≥ 0$. Show that $3|X_n$ for all $n ≥ 0$. I have the base case where $n=0$. Therefore $X_0=3$ and $3|0$. ...
0
votes
1answer
33 views

Combinatorial Proof: How many length-n lists can we form using the elements in {1,2,3} [PROOF]

I'm trying to prove that $2\times(3^0) + 2\times(3^1) + 2\times(3^2) + \cdots+ 2\times(3^(n-1)) = 3^n - 1$ by answering the question "how many length-n lists can we form using the elements in ...
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
57 views

Use induction to prove that a function is not one to one

Suppose that m and n are positive integers with m > n and f is a function from $\{1, 2,\ldots, m\}$ to $\{1, 2, \ldots , n\}$. Use mathematical induction on the variable n to show that f is not ...
-2
votes
0answers
42 views

Prove using Induction $ i(T) \leq 2^{h(t)} - 1$ in a full binary tree

Recursive Definitions for Full Binary Tree The height of a full binary tree, written $h(T)$, is dened recursively as follows. $h(T) = 0$ $h(T1 \cdot T2) = 1 + $max$\Big(h(T1), h(T2)\Big)$ The ...
1
vote
2answers
66 views

Prove $1(1!)+\dots+n(n!) = (n+1)!-1$ using induction

So I'm trying to prove this statement (through induction): $$1(1!)+2(2!)+\dots +n(n!)=(n+1)!-1$$ But I'm confused with the inductive step here: $$(n+1)!-1+[(n+1)(n+1)!] = (n+2)!-1$$ What do I do ...
-2
votes
0answers
68 views

Prove h(T) = log2l(T) in a complete binary tree using Induction

Recursive Definitions for Full Binary Tree The height of a full binary tree, written h(T), is dened recursively as follows. h(T) = 0 h(T1 T2) = 1 + max(h(T1); h(T2)) The number of nodes in a full ...
0
votes
1answer
65 views

Prove Complete Binary Tree using Induction

Recursive Definitions for Full Binary Tree The height of a full binary tree, written h(T), is dened recursively as follows. h(T) = 0 h(T1 T2) = 1 + max(h(T1); h(T2)) The number of nodes in a full ...
0
votes
2answers
55 views

Find the largest natural number m such that n$^3$-n is divisible by m for all n$\in$ $\mathbb{N}$.

Find the largest natural number m such that n$^3$-n is divisible by m for all n$\in$ $\mathbb{N}$. Prove your assertion. So my basis that I have is: Notice that (1)$^3$-(1)=0, and m(0)=0, so m ...
3
votes
5answers
153 views

Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$

I am trying to prove the summation formula using induction: $$\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$$ So far I have... Base case: Let n=1 and test $\frac{1}{k(k+1)} = 1-\frac{1}{n+1}$ ...
1
vote
2answers
39 views

conjecture and prove sequence value using induction

Conjecture and prove $a_n$ for $n\ge 0$. $a_n=\sum_{i=0}^{n-1}{{n-1}\choose {i}}a_ia_{(n-1)-i},n\ge 1; a_0 $ a fixed constant.
0
votes
1answer
56 views

proof by induction for summation

This is not a duplicate. I know my conjecture is right, just need to prove it, using induction(not Gauss Method). Conjecture formula from following equations, and prove conjecture: ...
0
votes
1answer
28 views

Prove for all integers, by induction

Define $\alpha = (1+ \sqrt{5})/2$. Define f(0) = 0, f(1) = 1, and f(n) = f(n-1) + f(n-2) for all $n\ge 2$. Prove, for all integers $n\ge 3, f(n) \gt \alpha^{n-2}$ I understand the base case, but how ...
0
votes
0answers
31 views

strong induction proof of sequence

Posting even though correct just for feedback, etc. $n_0,n_1$ are lower/upper bounds of true values for strong induction. Guess I could have used different values, like 2 and 3, or 1 and 2, but it ...
0
votes
1answer
19 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 ...
1
vote
1answer
45 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 ...
0
votes
1answer
30 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
0answers
72 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$$
2
votes
3answers
61 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, ...
1
vote
4answers
57 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 ...
0
votes
2answers
41 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 ...
1
vote
1answer
53 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
3answers
33 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
28 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
59 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)!$. ...
4
votes
8answers
142 views

Show that $n^3+2n$ is divisible by 3 for all $n\ge 1$

i want to prove it with mathematical induction : first i am tried with n=0 then it is divisible by zero then i move to next step change all n with K then i get this product : $$P(K)=K^3+2K = 3m$$ ...
1
vote
2answers
38 views

Proof an inequality by mathematical induction

I have a problem that I have to solve using mathematical induction but I'm stuck from a part. The problem is: Proof that $\large n<2^n$ is true for $\large n \in \mathbb{N}\ $ So, I did that ...
1
vote
3answers
50 views

Finishing Induction Step

I am currently writing a proof for the following problem $$ \sum\limits_{i=1}^n i^22^i = n^22^{n+1}-n2^{n+2}+3*2^{n+1}-6 $$ By induction on $n\ge0$ My question isn't really about how to correctly ...
0
votes
1answer
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 ...
1
vote
2answers
73 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.
1
vote
1answer
65 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).